当前位置：首页 > news >正文

从零开始学RSA:N不互素

news 来源：原创 2024/5/16 20:57:52

1.N不互素

两个n里使用有相同的素数p或q

在CTF中，同样一个e（一般为65537）和m，有两个或多个n和c时，那么n之间可能是共享素数

2.题目

n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073e = 65537m = bytes_to_long(flag)c = pow(m, e, n1)c = pow(c, e, n2)print("c = %d" % c)outputc = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264

此题相较于标准的N不互素题目略有改动，只给了一个密文c。

所以我们需要在给定的c2基础上解出c1，再根据解出的c1以及n不互素的特质求出的p,q1解出phi_n1和d,进而求出m

from Crypto.Util.number import *import  gmpy2n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073e = 65537c2 = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264p = gmpy2.gcd(n1,n2)q1 = n1//pq2 = n2//pphi_n1 = (p-1)*(q1-1)phi_n2 = (p-1)*(q2-1)d1 = gmpy2.invert(e,phi_n1)d2 = gmpy2.invert(e,phi_n2)c1 = pow(c2,d2,n2)m = pow(c1,d1,n1)flag = long_to_bytes(m)print(flag)

3.识别此类题目，通常会发现题目给了多个n，均不相同，并且都是2048bit，4096bit级别，无法正面硬杠，并且明文都没什么联系，e也一般取65537。

这种题目一般可以直接gcd(n1,n2)求出一个因数。

例题：攻防世界 (xctf.org.cn)

4.共模数攻击

假如Alice和Bob分别利用公钥e_1 ,e_2对明文M进行加密：

C_1=M^(e_1 ) (mod n)

C_2=M^(e_2 ) (mod n)

则可以分别利用私钥d_1 ,d_2进行解密：

M=C_1^(d_1 ) (mod n)

M=C_2^(d_2 ) (mod n)

假如攻击者监听获得了密文C1,C2，所有公钥都是公开的，那么攻击者在已知C1,C2,e1,e2,n的情况下，可以绕过d1,d2直接恢复出明文M。利用信息安全数学基础证明如下：

首先假设这些公钥共模且互素，即有gcd⁡(e_1,e_2 )=1，则

e_1x+e_2y=1

其中x，y皆为整数，一正一负；利用欧几里得扩展算法可以求得一组解（x，y），假设x为正，y为负，利用模运算的性质，因为

成功恢复明文M.

以下我以最近做过的一道CTFcrypt题目为例，演示RSA公共模数攻击，题目如下图，模数n长度为4096bit，

附其源码veryhardRSA.py文件，公钥分别为e1=17,e2=65537

#!/usr/bin/env pythonimport randomN = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929Ldef pad_even(x):return ('', '0')[len(x)%2] + xe1 = 17e2 = 65537fi = open('flag.txt','rb')fo1 = open('flag.enc1','wb')fo2 = open('flag.enc2','wb')data = fi.read()fi.close()while (len(data)<512-11):data  =  chr(random.randint(0,255))+datadata_num = int(data.encode('hex'),16)encrypt1 = pow(data_num,e1,N)encrypt2 = pow(data_num,e2,N)fo1.write(pad_even(format(encrypt1,'x')).decode('hex'))fo2.write(pad_even(format(encrypt2,'x')).decode('hex'))fo1.close()fo2.close()

# encoding: utf-8import syssys.setrecursionlimit(1000000) #设置为一百万N = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929Ldef pad_even(x):return ('', '0')[len(x)%2] + x#欧几里得扩展算法def extgcd(a, b):if a == 0:return (b, 0, 1)else:g, y, x = extgcd(b % a, a)return (g, x - (b // a) * y, y)#求模逆def modinv(a, m):g, x, y = extgcd(a, m)if g != 1:raise Exception('modular inverse does exist!')else:return x % mdef main():e_1 = 17e_2 = 65537fo1 = open('./flag.enc1', 'rb')fo2 = open('./flag.enc2', 'rb')fo3 = open('./flag_dec.txt', 'wb')data1 = fo1.read()data2 = fo2.read()fo1.closefo2.closec1 = int(data1.encode('hex'), 16)c2 = int(data2.encode('hex'), 16)g, x, y = extgcd(e_1, e_2)#求模反元素if x < 0:x = - xc1 = modinv(c1, N)elif y < 0:y = - yc2 = modinv(c2, N)if g == 1:m = (pow(c1, x, N) * pow(c2, y, N)) % Nfo3.write(pad_even(format(m,'x')).decode('hex'))fo3.closeif __name__ == '__main__':main()

成功获取到PCTF{M4st3r_oF_Number_Th3ory}，解密成功。

可见，在攻击者已知C1,C2,e1,e2,N时，可以在不知道私钥d1,d2的情况下恢复出明文M，如果不同的用户使用相同的模数。