RSA笔记

花了将近半天的时间学完了离散数学的第十一章，在这里做一下常见的rsa的分析。

rsa相关理论

首先在进行rsa加密之前会申请两个大素数，分别为p、q（一般会用getprime生成），计

1
n = p * q

根据欧拉函数求得

1
phi(n) = phi(p) * phi(q) = (p - 1) * (q - 1)

取一小于phi(n)的整数e作为加密的指数，这里的e在原则上要求与phi(n)互质，但是也会有遇到e与phi(n)不互质的情况，这里在之后会继续讲到。根据改e求出关于phi(n)的模反元素d，满足以下关系：

1
d * e ≡ 1 (mod phi(n))

注意上述的符号“≡”为同余符号，意义为左右两边的余数相同。

随后销毁p、q，这时(n,e)为公钥，(n,d)为私钥。

信息加密

在信息加密中，使用公钥对信息m进行加密，加密之后的密文c为：

1
c ≡ pow(m,e,n)

上式中的pow意思为指数并取余，等价于

1
c ≡ (m ** e) mod n
信息解密

在信息解密中，使用私钥对密文c进行解密，解密之后的明文m为：

1
m ≡ pow(c,d,n)

等价于：

1
m ≡ (c ** d) mod n
正确性证明

针对以上加密解密的是否正确，对齐进行证明：

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
已知：
d * e ≡ 1 (mod phi(n));
c ≡ (m ** e) mod n;
证明m ≡ (c ** d) mod n
证明：
要证m ≡ (c ** d) mod n
即证(c ** d) ≡ m mod n
又∵c ≡ (m ** e) mod n
即证(m ** ed) ≡ m mod n
又∵d * e ≡ 1 (mod phi(n))
∴d * e = k * phi(n) + 1
即证(m ** (k * phi(n) + 1)) ≡ m mod n
分类进行讨论
当gcd(m,n) = 1时：
(m ** (k * phi(n) + 1))
≡ m * (((m ** phi) mod n) ** k)
又∵gcd(m,n) = 1
∴(m ** phi) mod n ≡ 1 mod n
∴上式 ≡ m mod n

当gcd(m,n) ≠ 1时：
∵m = p * q
又∵p、q为素数且gcd(m,n) ≠ 1
∴m必为p或q的倍数
令m = x * p (x < q)
∵p为素数
∴m ** phi(q) ≡ 1 mod q
∴(m ** (k * phi(n) + 1))
≡ m * ((m ** (phi(n))) ** k)
≡ m * ((m ** ((p - 1) * phi(q))) ** k)
≡ m mod n

证明完了rsa的正确性，接下来介绍以下常见的rsa攻击，以及获取m的exp模板

rsa攻击

已知p、q、n、e，求m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2
import libnum
from libnum.primes import generate_prime
from libnum.strings import n2s, s2n
p = generate_prime(1024)
q = generate_prime(1024)
n = p * q
e = 65537
flag = "flag{aaa}"
c = pow(s2n(flag),e,n)
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
flag = n2s(pow(c,d,n))
print(flag)
n较小可直接进行分解

使用yafu进行整数分解

exp同上

n、e较大时使用RsaCtfTool进行攻击

exp同上

已知p、q、dp、dq

推导过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n = p * q
phi(n) = (p - 1) * (q - 1)
dp ≡ d mod (p - 1)
dq ≡ d mod (q - 1)
d * e ≡ 1 mod phi(n)
令m1 ≡ (c ** d) mod q；m2 ≡ (c ** d) mod p
c ** d = k * q + m1
m2 ≡ (k * q + m1) mod p
∵p为素数
∴m2 - m1 ≡ k * q mod p
又∵gcd(p,q) = 1
∴((m2 - m1) / q) ≡ k mod p
k ≡ ((m2 - m1) / q) mod p
根据先前所得：c ** d = k * q + m1
c ** d = (((m2 - m1) / q) mod p) * q + m1
m ≡ (c ** d) mod n
m ≡ ((((m2 - m1) / q) mod p) * q + m1) mod n
∵m1 ≡ (c ** d) mod q；m2 ≡ (c ** d) mod p
又∵dp ≡ d mod (p - 1)；dq ≡ d mod (q - 1)
∴m1 = (c ** (dq mod (q - 1))) mod q
m2 = (c ** (dp mod (p - 1))) mod p
将m1、m2代入m ≡ ((((m2 - m1) / q) mod p) * q + m1) mod n
得到最终的m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import gmpy2
import libnum
from libnum.strings import n2s

def decrypt(dp,dq,p,q,c):
    InvQ = gmpy2.invert(q, p)
    mp = pow(c, dp, p)
    mq = pow(c, dq, q)
    m = (((mp-mq)*InvQ) % p)*q+mq
    print (n2s(m))

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
decrypt(dp,dq,p,q,c)
已知dp、n、e

由于已经知道了e，所以只要知道p、q就可以对m进行求解，推导过程如下

1
2
3
4
5
6
7
8
9
10
11
12
c ≡ (m ** e) mod n
dp ≡ d mod (p - 1)
m ≡ (c ** d) mod n
d ≡ dp mod (p - 1)
c ** d ≡ (m ** (d * e)) mod n 
e * d ≡ 1 mod phi(n) ≡ 1 mod ((p - 1) * (q - 1))
d = k * (p - 1) + dp
e * dp * (1 mod (p - 1)) ≡ 1 mod ((p - 1) * (q - 1)) ≡ (1 mod (p - 1)) mod (1 - 1)
e * dp ≡ 1 mod (q - 1)
e * dp = k * (q - 1) + 1
p = ((e * dp - 1) / k) + 1
在此处对k进行爆破即可获得p
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import gmpy2
import libnum
e=65537
n = 16969752165509132627630266968748854330340701692125427619559836488350298234735571480353078614975580378467355952333755313935516513773552163392952656321490268452556604858966899956242107008410558657924344295651939297328007932245741660910510032969527598266270511004857674534802203387399678231880894252328431133224653544948661283777645985028207609526654816645155558915197745062569124587412378716049814040670665079480055644873470756602993387261939566958806296599782943460141582045150971031211218617091283284118573714029266331227327398724265170352646794068702789645980810005549376399535110820052472419846801809110186557162127
dp = 1781625775291028870269685257521108090329543012728705467782546913951537642623621769246441122189948671374990946405164459867410646825591310622618379116284293794090970292165263334749393009999335413089903796624326168039618287078192646490488534062803960418790874890435529393047389228718835244370645215187358081805
c = 0x6c78dcee37830f3ec4ab4989d40fbb595060b3fbc395d52ad26defc13372c1a3948c5388f4e450e46e016c7803133d6881e5efc3b90a4789448097c94124590b1e7949f2524d7edccd61a27691c18d090ac1f54643b563141306045417581e3b263f4ad2816136a48b106f3058b08e2a810f4ae8ef25916cc110b41ac8158ce69ecbe20fc60c1ddb20154c6646bc5142aefe47abf053a8ac949d5bc057bb18b191ad08070fe9ec5d76b1fceae685514532448c1b388b2d38e7241ac19c296e95e4e021a3a4015d909a1d53a2eb7fa86f6329f4e6c937f958be576c58fab4d9c9126999c99bb28718efc41a6f5db52b47942a2ddf21639f020b5489699cf22b46
 
for i in range(1,65538):
    if (dp*e-1)%i == 0:
        if n%(((dp*e-1)//i)+1)==0:
            p=((dp*e-1)//i)+1
            q=n//(((dp*e-1)//i)+1)
            phi = (p-1)*(q-1)
            d = gmpy2.invert(e,phi)%phi
            print(libnum.n2s(pow(c,d,n)))

已知n、e、d，求p、q

推导过程：

1
2
3
4
5
6
7
8
9
10
11
12
n = p * q
e * d ≡ 1 mod phi
phi = (p - 1) * (q - 1)
e * d = k * phi + 1
phi = (e * d - 1) / k = (p - 1) * (q - 1) = p * q - (p + q) + 1 = n - (p + q) + 1
p + q = phi - n - 1
令p + q = t
则p = t - q
n = p * q
n = q * (t - q) = -q ** 2 + q * t
q ** 2 - q * t + n = 0
其实p、q分别为上一元二次方程的两个解，接下去的判断就是一元二次方程根的判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import gmpy2
import libnum
n = 16352578963372306131642407541567045533766691177138375676491913897592458965544068296813122740126583082006556217616296009516413202833698268845634497478988128850373221853516973259086845725813424850548682503827191121548693288763243619033224322698075987667531863213468223654181658012754897588147027437229269098246969811226129883327598021859724836993626315476699384610680857047403431430525708390695622848315322636785398223207468754197643541958599210127261345770914514670199047435085714403641469016212958361993969304545214061560160267760786482163373784437641808292654489343487613446165542988382687729593384887516272690654309
e = 65537
d = 9459928379973667430138068528059438139092368625339079253289560577985304435062213121398231875832264894458314629575455553485752685643743266654630829957442008775259776311585654014858165341757547284112061885158006881475740553532826576260839430343960738520822367975528644329172668877696208741007648370045520535298040161675407779239300466681615493892692265542290255408673533853011662134953869432632554008235340864803377610352438146264524770710345273439724107080190182918285547426166561803716644089414078389475072103315432638197578186106576626728869020366214077455194554930725576023274922741115941214789600089166754476449453

temp = e * d - 1
# k = 1
for k in range(1,65537):
    phi = temp // k
    # print(k)
    if (phi * k == temp):
        t = n + 1 - phi
        delt = t ** 2 - 4 * n
        if (gmpy2.iroot(delt,2)[1]) and ((((t + int(gmpy2.iroot(delt,2)[0])) // 2) * 2) == (t + gmpy2.iroot(delt,2)[0])):
            p = (t + int(gmpy2.iroot(delt,2)[0])) // 2
            q = n // p
            if (p * q == n):
                print("p =",p)
                print("q =",q)
                break
        else:
            continue
n分解出不止两个因数

这里其实考察的是欧拉公式的本质

1
2
n = p1 * p2 * p3
phi(n) = (p1 - 1) * (p2 - 1) * (p3 - 1)

接下来的步骤就和已知p、q求m一样

低加密指数分解攻击

在加密过程中，对e选择可以说是任意的，但是如果e的取值太小，会造成安全问题，下面分别对e=2和e=3进行讨论

e=2

当e=2时，在进行加密的时候，相当于只是对明文进行了平方处理，只需要对密文进行开方或者加上几个n即可

1
2
3
4
5
6
7
8
import gmpy2
import libnum
from libnum.strings import n2s
c = 9217979941366220275377875095861710925207028551771520610387238734819759256223080175603032167658086669886661302962985046348865181740591251321966682848536331583243529
m = gmpy2.iroot(c,2)
m = int(m[0])
flag = n2s(m)  #将 十六进制转为 字符
print(flag)
e=3

当e为3的时候，加密过程也就是对明文进行立方处理，可能会大于n，那就需要进行爆破n的个数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import gmpy2
import libnum
from libnum.strings import n2s
n = 62238551978433838001498457736429006991865583728626132139136256391485968857741649418990547571437762934449868634562245286176618471355786138381567476265484214608900167440511382125259943558246159258716213963735131393428605626773031068644321261445284230749457763679689698230585197310945795260304584991080604702929
e = 3
c = 184706733600030961911836917506112422167545490484023895702890946835667701083139603160422181673643482375812680575389095142687410989330788033710088246782628789557043348703224329521695342998531932006194716597523162472306119232610211018033794397444557249275490146884605734496362904120178078821

k = 0
while 1:
    flag = gmpy2.iroot(c+k*n,e)
    if(flag[1]):
        flag = n2s(int(flag[0]))
        print(flag)
        break
    else:
        k += 1
共模攻击

使用相同的模数 N 、不同的私钥，加密同一明文消息，即对同一个明文m，使用不同的e对其进行加密，这里需要用到的数学理论为扩展欧几里得算法：

1
2
3
4
5
6
7
8
9
10
11
c1 ≡ (m ** e1) mod n
c2 ≡ (m ** e2) mod n
e1 * d1 ≡ 1 mod n
e2 * d2 ≡ 1 mod n
必存在a、b，使得整式a * e1 + b * e2 = 1成立
a,b = gcdext(e1,e2)
c1 ** a ≡ (m ** (a * e1)) mod n
c2 ** b ≡ (m ** (b * e2)) mod n
将两式相乘
c1 ** a * c2 ** b ≡ (m ** (a * e1 + b * e2)) mod n ≡ m mod n
m ≡ (c1 ** a * c2 ** b) mod n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import getPrime, long_to_bytes
import gmpy2
import libnum
from libnum.strings import n2s, s2n
p = getPrime(50)
q = getPrime(50)
n = p * q
e1 = 17
e2 = 65537
m = "flag{aaaaa}"
m = s2n(m)
c1 = pow(m,e1,n)
c2 = pow(m,e2,n)
_,a,b = gmpy2.gcdext(e1,e2)
assert(a*e1+b*e2 == _)
flag = (pow(c1, a, n) * pow(c2, b, n)) % n
print(n2s(flag))
e与phi不互素

这种情况为当我们顺利的求出p、q之后，结果计算模反元素时发现e与phi(n)不互素

m ** (gcd(e,phi(n))) < n

这种情况比较容易理解，和低加密指数分解类似：

1
2
3
4
5
6
7
n = p * q
c ≡ (m ** e) mod n
phi(n) = (p - 1) * (q - 1)
gcd(e,phi(n)) = t
e = e1 * t
c ≡ (m ** (e1 * t)) mod n
将m ** t看成一个整体，利用e1和phi求出模反元素，接出m ** t，再将求解出来的进行开t次方，条件是t不是很大
e ≠ 2且e | phi(n)

在这里，e不仅与phi(n)不互素，e反而成了phi(n)的一个因数，可以利用amm算法进行实现。
amm算法的python实现，但是需要用sagemath跑脚本

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import random
from Crypto.Util.number import long_to_bytes

def AMM(o, r, q):

    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))

    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            j = - discrete_log(d, a)
        b = b * (c^r)^j
        h = h * c^j
        c = c^r
    result = o^alp * h
    return result

def findAllPRoot(p, e):
    proot = set()
    while len(proot) < e:
        proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
    return proot

def findAllSolutions(mp, proot, cp, p):
    all_mp = set()
    for root in proot:
        mp2 = mp * root % p
        assert(pow(mp2, e, p) == cp)
        all_mp.add(mp2)
    return all_mp


c = 15433214846771804225704093824935372144929516863829752998270111032551363583267576397009018518790803908369965458162930857063271509296349091229352855725285388975497906340053281554202527432848881160125418406408621879995822551367228501163128699032015069585502994319524445505522625561831240862136447585120010288772692097621553249775117843166714346924868089146429002417223863834435968726551668931140147337199939823985783939085842479154589529244209712172799274024573845157268545992888944742377166586536479490962335287124809557709167220756920767331929168230518135523463578566851417486746667008938122693256033127001185017237773
p = 0xa892eb59b175bcf896be2176598f278437fe10ef032279f06e1092143acfb3c16b31811cca5286699595c2720c652ee64f8adc92c8b16a5601dd981d6f839ce9c0513db30de88c2ec6cae1a726acbd235ea946631bde633707d766287a2f075e9aace1606bd8b4f52d4f5b87dfb81f14fbc5338004575e9430257e180a169eff
q = 0xe3d47225b77e56129dc3fed716181845f89fa15b2eb35453ffdc0f05cdf57c0d90410911d209818e886b202bc4893ebe85a07ef670122f0e70092de1b7963c3b24a58c6a9ec9ed677db3473b1882d10d550e45c18fd57b85a70a5401a074d36760e85c7e6258f0ab08fa69cd433709910fad6e145f7b85f589e83d61d3baf6ad
n = p * q
e = 0x3
cp = c % p
cq = c % q
mp = AMM(cp, e, p)
mq = AMM(cq, e, q)
p_proot = findAllPRoot(p, e)
q_proot = findAllPRoot(q, e)
mps = findAllSolutions(mp, p_proot, cp, p)
mqs = findAllSolutions(mq, q_proot, cq, q)
print("mps=",mps)
print("mqs=",mqs)


flag = []
for mpp in mps:
    for mqq in mqs:
        solution = CRT_list([int(mpp), int(mqq)], [p, q])
        flag.append(solution)
print("flag=",flag)

例题已知p、n、e，对flag进行筛选：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
c = 15433214846771804225704093824935372144929516863829752998270111032551363583267576397009018518790803908369965458162930857063271509296349091229352855725285388975497906340053281554202527432848881160125418406408621879995822551367228501163128699032015069585502994319524445505522625561831240862136447585120010288772692097621553249775117843166714346924868089146429002417223863834435968726551668931140147337199939823985783939085842479154589529244209712172799274024573845157268545992888944742377166586536479490962335287124809557709167220756920767331929168230518135523463578566851417486746667008938122693256033127001185017237773
p = 0xa892eb59b175bcf896be2176598f278437fe10ef032279f06e1092143acfb3c16b31811cca5286699595c2720c652ee64f8adc92c8b16a5601dd981d6f839ce9c0513db30de88c2ec6cae1a726acbd235ea946631bde633707d766287a2f075e9aace1606bd8b4f52d4f5b87dfb81f14fbc5338004575e9430257e180a169eff
q = 0xe3d47225b77e56129dc3fed716181845f89fa15b2eb35453ffdc0f05cdf57c0d90410911d209818e886b202bc4893ebe85a07ef670122f0e70092de1b7963c3b24a58c6a9ec9ed677db3473b1882d10d550e45c18fd57b85a70a5401a074d36760e85c7e6258f0ab08fa69cd433709910fad6e145f7b85f589e83d61d3baf6ad
n = p * q
e = 0x3
flag= [16399975821954318279221498470275521146084468474951947690849471303696067145089454840116636668718094830771604329504802271219147143674615173355400952708408746368044309638665492578797050592110356801725854406347821079081157487918992622400462465388082464774696448382685479944891218685238696458096657412926524712567669614565532058043579724279426556454939680807472739837985809673799969798738593585980694664789237839687687796230523379344762186979226349278188873930789783857039091180416888435596976167786057695368710150520870289607521049807301430045313742380064830918865207342030577149859823652984530212731974224763950142974621, 118376620831769511477866973072371934475020796752620925673118534551164773446938312398569573679592158603383872824973732698728390995878086711747236172795750569226610200641434547443746623460729162322168208115247321277147882591962895515811370349077174567949437554802765321577395084044034054316894295810117788487548, 2636318234956593740025392750115188144201643355150271367205885378997179090543819773476577550528375163758510881992249744774524837065489772391156037111732467139693340916788711638687169314077851149378307041485634962316435620167189448246015443556715342171784808908063399612060691731983276962947560584384335316122282037142086941835032738329850136894931990705161961038218917946748067094287897131597506323689531027690334541348560039800989704389300502732058283731159165628739251642679570408402108118104583164460322951459558839451931706278697205870900622234858961063581108199081076817814272087232781399673277754759478621882611, 6499923879915138342858869356582590861130291995517603812052133716178234746533241737483268105124561484329319690969270714817941158351001302244375332727987416718695298178049259665052620644321602664094820510278569361228681031817116243817011512080214536206408407155105866448471154438346652800633930600912186263889013394664316661787502455744483605331139029724777749672860598784630335665820774628981390708884654060406739800168399577656663475628461891448512238948421204060693304430762642930211936422386082993349344387307942221577378260788732589892542175026796700340977171479382730295803171335098970494264976431029903834527839, 9038736347580887208116294651480505977356892520242549511647711958794851966958323505447060125433998050906882218022887300278018435418965579910075201650274907495269211152612176575799922287905990204213405299522446763227582381644794647411659403174315339338373641745624661179320713968225376165502623845152726404589025779394696194970808455124099506923873095191936477520729599452091871779445992192681266604024563857734525193290538837872322511703407147432634320575991291892781790092162090370420611963311513027732755758650739228065261169314032678111718633554934739976611621640149523099062104079362706499829930561360922499291537, 11675054582537480948141687401595694121558535875392820878853597337792031057502143278923637675962373214665393100015137045052543272484455352301231238762007374634962552069400888214487091601983841353591712341008081725544018001811984095657674846731030681510158450653688060791381405700208653128450184429537061720711189439915951367294363326480877271884330065100345817633275398864288774100286951011880203354034502726821475861814125144974583825096829563452945368134354706952294431534200226231378973457955367029870910501995050746240044993000766988466807885440716526472243292284427834595298981082551453845186314020310283332686600, 7263733707082586196337236363577742140752533124284072511591452208520653308012393329156791013065158182683773756543281811626681148258124098719869582868688862509655670543827521275057260633710902988252726854583616755536040835934686930337435509751152586396503232319516213884359372514908766694515166227630003132556255806138296684909566663232020442294393639580780408201233174407870402265182983513003228058535460592987229581888590029188380615965585868385871115078413663598379924906333240549539185003834662375236874603638121907301063200147908738766059574769331994946357490108764004714664985146608744264476825743164449898076623, 9802546174748335061594661658475657256979133649009018211187030451137270528437475097120583033374594749261336283596898397086758425326088376385569451790976353286229583518390438185804562277295290528371311643827494157534942185762365333932083400845253389528468466910035008615208932044787490059383859471870543273256268190868676218092872662611636343887127705047939136049102175075331938378808201076703103953675370390315014975010729289404039652040531124369993196705983751430468410567732687989747860544760092409620285974980918913788946108673208826985236033297470034581991940269530797517923917890872480270041779873495468562840321, 12438864409704928801620054408590845401180777004159289578392915830134449618981294870597160583902969913019847165589148141861283262391578148776725488902708820425922924435179149824491731591373141677749618685313129119851377805929554782178098844401968731700253275818098408227269623776770767022331420056254878589378431851389931390416427533968414108847584674956348476161647974487528840699649159895902040703685309259401965643534315596506300965433953540390304244264347166489981052009770823850706222039403946411758440718325230431963729932359943137340325285183251821077623610913809109014160794894061227615398163332444829396235384]

for i in range(len(flag)):
    assert (((flag[i] ** 3)) % n == c)
    f = long_to_bytes(flag[i] - p)
    if b"DAS" in f:
        print(f)
        break
    else:
        print("No flag.")
        continue
已知n、p的前几位

这种题目一般来说会对p做一个移位的处理，例如下面这个题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from secret import flag
p = getPrime(1024)
q = getPrime(1024)
assert len(flag) == 40
n = p*q
m = bytes_to_long(flag)
e = 3
c = pow(m+p, e, n)

print("n =", n)
print("p =", hex((p>>400)<<400))
print("c =", c)
print("p =", hex(p))
'''
n = 18938788289620067144478923765173436262311068999676893390445049546312684365514536608080428689027531397349166856558418856679224420742579451021100821630696237144618222613228409489544352235694744341844439195591698481080058837746671025995110356482183267906661682973204274675740778215117419822965350657167064853267563622675079821715407856685970086113198725477878846760181691806710341138916872837282000986249555478412089316527688906861692832058293518550563719385564121119900966641174901328361905085250758567429953313748419974818256075740638622748678830559125695986550219947994604631541361313204232163980034059284851019250771
pbar = 0xa892eb59b175bcf896be2176598f278437fe10ef032279f06e1092143acfb3c16b31811cca5286699595c2720c652ee64f8adc92c8b16a5601dd981d6f839ce9c0513db30de88c2ec6cae1a726ac0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
c = 15433214846771804225704093824935372144929516863829752998270111032551363583267576397009018518790803908369965458162930857063271509296349091229352855725285388975497906340053281554202527432848881160125418406408621879995822551367228501163128699032015069585502994319524445505522625561831240862136447585120010288772692097621553249775117843166714346924868089146429002417223863834435968726551668931140147337199939823985783939085842479154589529244209712172799274024573845157268545992888944742377166586536479490962335287124809557709167220756920767331929168230518135523463578566851417486746667008938122693256033127001185017237773
'''

我们发现这边p的后400位都被置为了0，那也有办法对p进行泄露，脚本同样需要用sage跑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = 18938788289620067144478923765173436262311068999676893390445049546312684365514536608080428689027531397349166856558418856679224420742579451021100821630696237144618222613228409489544352235694744341844439195591698481080058837746671025995110356482183267906661682973204274675740778215117419822965350657167064853267563622675079821715407856685970086113198725477878846760181691806710341138916872837282000986249555478412089316527688906861692832058293518550563719385564121119900966641174901328361905085250758567429953313748419974818256075740638622748678830559125695986550219947994604631541361313204232163980034059284851019250771
p_fake = 0xa892eb59b175bcf896be2176598f278437fe10ef032279f06e1092143acfb3c16b31811cca5286699595c2720c652ee64f8adc92c8b16a5601dd981d6f839ce9c0513db30de88c2ec6cae1a726ac0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

def leak_p(p_fake):
    pbits = p_fake.nbits()
    kbits = 400  #p lost
    pbar = p_fake & (2^pbits-2^kbits)
    PR.<x> = PolynomialRing(Zmod(n))
    f = x + pbar
    
    x0 = f.small_roots(X=2^kbits, beta=0.4)[0]
    p= x0 + pbar
    print (p)
leak_p(p_fake)
赏

谢谢你请我吃糖果

微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

ZhouYetao<br><br> 二进制略懂一点<br> 文件下载：https://github.com/zhouyetao/blog.git