Given d and e, factorize N to attack RSA

题目如下：

RSA算法的使用一般要求每个不同的用户有一个独立的模数N。有天，Bob脑洞大开，认为似乎没有必要这样做。只需要一个模数N，然后给不同的用户分发不同的e和d就好了。可惜这种做法有严重的安全漏洞。

给定Alice的公钥（e1，N），Adv为了破解Alice的密文，他也注册一个公私钥对，得到(e2, d2, N)，然后他就可以巧妙地计算出Alice的解密私钥。注意：Adv得到的私钥不一定与Alice的相同，只是它确实可以解密。

（e1 =

44379563805854841580307748547737435172564831877127303051909203409873174780389273150966396080375621148040275710628408649117613085199533826455458312376264659153842853015345496268736337902730232293424031775369541079662258443836020140399047886828048837071536578243295077689245549921524765222192270061081366989243

N =

188115669939527035644766943794256836704505079895306601119938518634078379404429524926183546093986493443422022468844644307633083886388295943602507953702360632321739073592477683222131866451975315695813478098524853358977564134499058448438525811837376172990710150323209055804682074564005014776547535959114226010493

）

(e2 =

112465763139808984065405993827008716763974555200543206549100182421914260511395374512318119557311872118857352370325610769529155517454000609905909538235321637165438962672069969201523246380106126889874030417878823876408727390390051948217715186480658609481138938023687641185709391304878382079926539531855678365763

d2 =

55881649455902117785162844948995531081646760354831350250450328774662614334096209227124014992837725793190883247171284132768863157972472923057215962250425474753160669444247876851199006665484502793278672692761545198268608005712388135980371518592854149756626148424994498979112285655516912703587302199972664162731

N =

)

求解(e1, N)加密得到的密文（没有编码，是一个整数）：

166834578157098529809222592291594342260836191039081705782260506690911922650094691879568641873546447862853989518762075081785381252999566333779425586950217410876199240677942391128773211264433855236931134494842223272683014826519273429450763047329625425561073729238027952900168036140503255431512655421527963913597

请解释过程，给出明文及其解密用的私钥。

一开始想，给定的N相同，是不是共模攻击，看并不满足共模攻击的条件

后来看到一篇博客（http://jackyc.top/2018/10/27/RSA-3/#more），里面有个参考文档（https://www.di-mgt.com.au/rsa_factorize_n.html），看完后知道原来知道(e,d,N)可以分解N，但是原理还不是很理解

找到了一个PDF，里面有原理的讲解，不过里面有些小地方和我的理解有出入，要么我错了，要么PDF出现小错误，最后还是按自己的理解和各种参考资料用python写了一下

Given d and e, factorize N to attack RSA

e1 = 44379563805854841580307748547737435172564831877127303051909203409873174780389273150966396080375621148040275710628408649117613085199533826455458312376264659153842853015345496268736337902730232293424031775369541079662258443836020140399047886828048837071536578243295077689245549921524765222192270061081366989243

N = 188115669939527035644766943794256836704505079895306601119938518634078379404429524926183546093986493443422022468844644307633083886388295943602507953702360632321739073592477683222131866451975315695813478098524853358977564134499058448438525811837376172990710150323209055804682074564005014776547535959114226010493

e2 = 112465763139808984065405993827008716763974555200543206549100182421914260511395374512318119557311872118857352370325610769529155517454000609905909538235321637165438962672069969201523246380106126889874030417878823876408727390390051948217715186480658609481138938023687641185709391304878382079926539531855678365763

d2 = 55881649455902117785162844948995531081646760354831350250450328774662614334096209227124014992837725793190883247171284132768863157972472923057215962250425474753160669444247876851199006665484502793278672692761545198268608005712388135980371518592854149756626148424994498979112285655516912703587302199972664162731

c = 166834578157098529809222592291594342260836191039081705782260506690911922650094691879568641873546447862853989518762075081785381252999566333779425586950217410876199240677942391128773211264433855236931134494842223272683014826519273429450763047329625425561073729238027952900168036140503255431512655421527963913597

from random import randint

import gmpy2

def oddR(r):

    while r%2==0:

        r=r//2

    return r

def bits(b):

    k=[]

    while b:

        if b%2!=0:

            k.append(1)

        else:

            k.append(0)

        b>>=1

    k.reverse()      #对于List等Sequence等类型的变量，比如此处的List变量，其内置函数reverse，是直接操作变量本身，调用reverse后，变量本身的值就是reverse后的值了，所以不能出现：kk=k.reverse()这样的操作

    return k

def quickmod(a,b,n):      #a^b mod n 快速幂模n运算

    f=1

    k=bits(b)

    for i in range(len(k)):

        f=(f*f)%n

        if k[i]:

            f=(f*a)%n

    return f

def gcd(m,n):

    while(n!=0):

        m,n=n,m%n

    return m

def func(e,d,N):

    k=e*d-1             #k是一个even number

    r=oddR(k)           #求出k=2^t*r中的r

    while True:

        b=randint(2,N-1)    #获取区间(2,N-1)的一个随机数

        a=quickmod(b,r,N)   #求解出b^r mod N的值

        if a==1:            #如果求得的a=1,则需要重新获取一个随机数b

            continue

        y=gcd(a-1,N)

        if a>1 and y>1:     #a要大于1,

            q=N//y

            return q

        else:

            r=r*2         #如果不满足的话,b就平方 a0 = br, a1 = (a0)^2, a2 = (a1)^2,…, ak = (ak-1)^2

#print(func(3,16971,25777))

def deciphering(e1,e2,d,N,c):    #e1用来求解p和q,e2用来求解e2*d=1 (mod)

    p=func(e1,d,N)

    q=N//p

    phi=N-(p+q)+1          #N和phi之间的关系

    d=gmpy2.invert(e2,phi)    #得到e2对应的私钥d

    m=gmpy2.powmod(c,d,N)

    return d,m

d,m=deciphering(e2,e1,d2,N,c)

print("The private key is:",d)

print("The message is:",m)

结果：

明文为：131

密钥为：72818963105077629740558410461847080457967247911531271148355717844840007560618118158503931879141520737129717539191898962908710378608064897528018640573684648011556192613882739251759874374669201358126911422986850885586463283920904391451268159684723197972233648239891580239064904439566608991520126027809037410483

秒客网

Given d and e, factorize N to attack RSA

相关文章