狗儿

热爱的话就坚持吧~

0%

菜鸡的RSA练习

发表于 更新于 分类于 ，

一些做过的RSA题目。RSA一直是菜鸡我的弱项。
（之前是私密状态，弃坑了算是，公开权限吧）

LHY

题目给出LHY.py和data。

LHY.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#!/usr/bin/env python

import gmpy
from Crypto.Util.number import *
from secret import x, y, flag

assert gmpy.is_prime(y) ** 2016 + gmpy.is_prime(x+1) ** 2017 + ((x**2 - 1)**2 % (2*x*y - 1) + 2) ** 2018 == 30097557298197417800049182668952226601954645169633891463401117760245367082644152355564014438095421962150109895432272944128252155287648477680131934943095113263121691874508742328500559321036238322775864636883202538152031804102118831278605474474352011895348919417742923873371980983336517409056008233804190890418285814476821890492630167665485823056526646050928460488168341721716361299816947722947465808004305806687049198633489997459201469227952552870291934919760829984421958853221330987033580524592596407485826446284220272614663464267135596497185086055090126893989371261962903295313304735911034185619611156742146

p = gmpy.next_prime(x**3 + y**3)
q = gmpy.next_prime(x**2*y + y**2*x)
n = p * q
phi = (p-1)*(q-1)
d = gmpy.invert(0x10001, phi)
enc = pow(bytes_to_long(flag), 0x10001, n)
print 'n =', n
print 'enc =', enc

data

1
2
n = 260272753019642842691231717156206014402348296256668058656902033827190888150939144319270903947159599144884859205368557385941127216969379550487700198771513118894125094678559478972591331182960004648132846372455712958337042783083099376871113795475285658106058675217077803768944674144803250791799957440111855021945690877200606577646234107957498370758707097662736662439460472126493593605957225541979181422479704018055731221681621886820626215670393536343427267329350730257979042198593215747542270975288047196483958369426727778580292311145109908665004662296440533724591193527886702374790526322791818523938910660223971454070731594803459613066617828657725704376475527288174777197739360634209448477565044519733575375490101670974499385760735451471034271880800081246883157088501597655371430353965493264345172541221268942926210055390568364981514774743693528424196241142665685211916330254113610598390909248626686397970038848966187547231199741
enc = 73933313646416156737449236838459526871566017180178176765840447023088664788672323530940171469589918772272559607026808711216932468486201094786991159096267208480969757088208089800600731106685561375522764783335332964711981392251568543122418192877756299395774738176188452197889668610818741062203831272066261677731889616150485770623945568369493256759711422067551058418926344060504112146971937651406886327429318390247733970549845424064244469193626197360072341969574784310397213033860597822010667926563087858301337091484951760613299203587677078666096526093414014637559237148644939541419075479462431789925219269815364529507771308181435591670281081465439913711912925412078002618729159141400730636976744132429329651487292506365655834202469178066850282850374067239317928012461993443785247524500680257923687511378073703423047348824611101206633407452837948194591695712958510124436821151767823443033286425729473563002691262316964646014201612

脚本及思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from Crypto.Util.number import *
from gmpy2 import *

# assert gmpy.is_prime(y) ** 2016 + gmpy.is_prime(x+1) ** 2017 + ((x**2 - 1)**2 % (2*x*y - 1) + 2) ** 2018 == 30097557298197417800049182668952226601954645169633891463401117760245367082644152355564014438095421962150109895432272944128252155287648477680131934943095113263121691874508742328500559321036238322775864636883202538152031804102118831278605474474352011895348919417742923873371980983336517409056008233804190890418285814476821890492630167665485823056526646050928460488168341721716361299816947722947465808004305806687049198633489997459201469227952552870291934919760829984421958853221330987033580524592596407485826446284220272614663464267135596497185086055090126893989371261962903295313304735911034185619611156742146

big_num = 30097557298197417800049182668952226601954645169633891463401117760245367082644152355564014438095421962150109895432272944128252155287648477680131934943095113263121691874508742328500559321036238322775864636883202538152031804102118831278605474474352011895348919417742923873371980983336517409056008233804190890418285814476821890492630167665485823056526646050928460488168341721716361299816947722947465808004305806687049198633489997459201469227952552870291934919760829984421958853221330987033580524592596407485826446284220272614663464267135596497185086055090126893989371261962903295313304735911034185619611156742146
print(iroot(big_num-2, 2018))
print(iroot(big_num-1, 2018))
print(iroot(big_num, 2018))
# output:
# (mpz(2), True)
# (mpz(2), False)
# (mpz(2), False)
# 所以gmpy.is_prime(y) ** 2016 和 gmpy.is_prime(x+1) ** 2017均等于1
# 所以y和x+1均为素数

# 尝试一下(x**2 - 1)**2 % (2*x*y - 1)是不是等于0
# 即测试2 ** 2018 是不是等于big_num - 2
print(2 ** 2018 == big_num - 2) 
# output = True
# 所以(x**2 - 1)**2 % (2*x*y - 1)是等于0的
# 即(x**2 - 1) ** 2能被2xy-1整除

# 很明显y = x/2的时候，整除关系成立。可以猜测x = 2y
# 带入，有p = gmpy.next_prime(9 * y**3)，q = gmpy.next_prime(6 * y**3)
# 根据素数的分布的定律，[next_prime(x) - x]一般不超过1000.
# 所以可以近似看作p = 9 * y**3, q = 6 * y**3
# 即n近似等于54 * y**6，前后误差一般不超过10**6
# 所以我们可以通过上面的关系，利用给出的n，借助中间变量y，得到p的一个近似值。
# 通过爆破确定p的真实值，然后就可以分解n了。
n = 260272753019642842691231717156206014402348296256668058656902033827190888150939144319270903947159599144884859205368557385941127216969379550487700198771513118894125094678559478972591331182960004648132846372455712958337042783083099376871113795475285658106058675217077803768944674144803250791799957440111855021945690877200606577646234107957498370758707097662736662439460472126493593605957225541979181422479704018055731221681621886820626215670393536343427267329350730257979042198593215747542270975288047196483958369426727778580292311145109908665004662296440533724591193527886702374790526322791818523938910660223971454070731594803459613066617828657725704376475527288174777197739360634209448477565044519733575375490101670974499385760735451471034271880800081246883157088501597655371430353965493264345172541221268942926210055390568364981514774743693528424196241142665685211916330254113610598390909248626686397970038848966187547231199741
e = 0x10001
enc = 73933313646416156737449236838459526871566017180178176765840447023088664788672323530940171469589918772272559607026808711216932468486201094786991159096267208480969757088208089800600731106685561375522764783335332964711981392251568543122418192877756299395774738176188452197889668610818741062203831272066261677731889616150485770623945568369493256759711422067551058418926344060504112146971937651406886327429318390247733970549845424064244469193626197360072341969574784310397213033860597822010667926563087858301337091484951760613299203587677078666096526093414014637559237148644939541419075479462431789925219269815364529507771308181435591670281081465439913711912925412078002618729159141400730636976744132429329651487292506365655834202469178066850282850374067239317928012461993443785247524500680257923687511378073703423047348824611101206633407452837948194591695712958510124436821151767823443033286425729473563002691262316964646014201612
y_jinsi = iroot(n//54, 6)[0]
p_jinsi = 9 * y_jinsi ** 3
for i in range(-500, 500):
    p = p_jinsi + i
    # 一个有趣的思路是爆破p而不是爆破n，能将爆破量下降到平方根。
    if (n % p == 0):
        print(p)
        q = n // p
        phi = (p-1) * (q-1)
        d = inverse(e, phi)
        m = pow(enc, d, n)
        msg = long_to_bytes(m)
        print(msg)
        break

参考飘零学长的https://www.anquanke.com/post/id/158533

baby_rsa

原地tp