从零开始学RSA:N不互素

1.N不互素

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

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

2.题目

n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061

n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073

e = 65537

m = bytes_to_long(flag)

c = pow(m, e, n1)

c = pow(c, e, n2)



print("c = %d" % c)



output

c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264

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

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

from Crypto.Util.number import *

import  gmpy2

n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061

n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073

e = 65537

c2 = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264



p = gmpy2.gcd(n1,n2)

q1 = n1//p

q2 = n2//p

phi_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 python



import random



N = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L



def pad_even(x):

    return ('', '0')[len(x)%2] + x



e1 = 17

e2 = 65537




fi = 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))+data



data_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-8

import sys

sys.setrecursionlimit(1000000) #设置为一百万



N = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L



def 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 % m



def main():

    e_1 = 17

    e_2 = 65537



    fo1 = open('./flag.enc1', 'rb')

    fo2 = open('./flag.enc2', 'rb')

    fo3 = open('./flag_dec.txt', 'wb')



    data1 = fo1.read()

    data2 = fo2.read()

    fo1.close

    fo2.close



    c1 = int(data1.encode('hex'), 16)

    c2 = int(data2.encode('hex'), 16)



    g, x, y = extgcd(e_1, e_2)

    #求模反元素

    if x < 0:

        x = - x

        c1 = modinv(c1, N)

    elif y < 0:

        y = - y

        c2 = modinv(c2, N)

    if g == 1:

        m = (pow(c1, x, N) * pow(c2, y, N)) % N

        fo3.write(pad_even(format(m,'x')).decode('hex'))

    fo3.close



if __name__ == '__main__':




    main()

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

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