RSA-e与φ(n)不互素

• e与φ(n)不互素

  $gcd(e,φ(n)) = b$

  $ed ≡ 1\ mod\ φ(n)$

  $e = ab$

  $abd ≡ 1\ mod\ φ(n)$

  $m^{ab} ≡ c\ mod\ n$

  $m^{abbd} ≡ c^{bd}\ mod\ n$

  $m^{abbd} ≡ m^b\ mod\ n$

  a与φ(n)互素，可确定唯一bd，求解$m^{b}\ mod\ n$

  $bd = invert(a,φ(n)) $

  若b过小如b=3，可以爆破出m

  若b过大，有两组数据且

  $gcd(n_1,n_2) = p$

  $gcd(e_1,φ(n_1)) = b$

  $gcd(e_2,φ(n_2)) = b$

  求出两个bd，得到两个同余式

  $x_1 ≡ m^b\ mod\ n_1$

  $x_2 ≡ m^b\ mod\ n_2$

  $y ≡ m^b\ mod\ p$

  $y ≡ m^b\ mod\ q_1$

  $y ≡ m^b\ mod\ q_2$

  中国剩余定理计算出特解Y

  $Y ≡ m^b\ mod\ q_1q_2$

  转化为另一个题目

  • 例子

    from libnum import *
    import gmpy2
    from rsa import transform
    p = 109935857933867829728985398563235455481120300859311421762540858762721955038310117609456763338082237907005937380873151279351831600225270995344096532750271070807051984097524900957809427861441436796934012393707770012556604479065826879107677002380580866325868240270494148512743861326447181476633546419262340100453
    q1q = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088835693
    q1p = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088834871
    e1 = 15218928658178
    e2 = 381791429275130
    q1=q1p
    q2 =  114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959513
        
    c1 =  262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124
    c2 =  7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596
    n1 = p*q1
    n2 = p*q2
        
    p=gcd(n1,n2)
    q1=n1/p
    q2=n2/p
        
    f1=(p-1)*(q1-1)
    f2=(p-1)*(q2-1)
    tmp=14
        
    e1=e1/tmp
    e2=e2/tmp
    bd1=invmod(e1,f1)
    print()
    bd2=invmod(e2,f2)
        
    m1=pow(c1,bd1,n1)
    m2=pow(c2,bd2,n2)
    print(m1)
    print(m2)
    m3=m1%p
    m2=m2%q2
    m1=m1%q1
        
    m=solve_crt([m1,m2,m3], [q1,q2,p]) 
    n=q1*q2
    f=(q1-1)*(q2-1)
    m=m%n
    d2=invmod(7,f)
    m=pow(m,d2,n)
    p = gmpy2.iroot(m, 2)[0]
    plaintext = transform.int2bytes(p)
    print(plaintext)