e与φ(n)不互素时

摘自大佬博客：e与φ(n)不互素时 | happi0 (gitee.io)

当gcd(e,φ(n)) != 1 的一些思路(非脚本!)

1. m ** GCD < n时

原理:

首先,找出gcd

1
gcd(e,φ(n)) == t

那么可以找到e’满足

1
e' = e // t

此时,显然gcd(e’,phi) =1,于是

1
2
3
e * d = 1 + k * phi
(e // t) * (d * t) = 1 + k * phi
e' * (d*t) = 1 + k * phi

所以可以求出dt,那么我们如何通过dt 解密呢

根据rsa基本原理,我们可以得到如下等式:

1
c ** d mod n == m
1
c ** d == m + k*n

等式两边同时t方

1
c ** (d*t) == m**t + K*n

同时mod n得到

1
c ** d*t mod n == m**t

所以,只需把d*t当作私钥解密得到的数字开t次方即可

条件:

对于式子

1
c ** d*t == m**t + K*n

由于结果了一次mod n运算,所以t必须满足

1
m ** t < n

否则会在mod n时丢失数据

2. n < m ** gcd < k * n

原理:

同上

条件:

对于式子

1
c ** d*t == m**t + K*n

当k很小时,可以考虑爆破k直到等式左边能被开d*t方

3.需要通过CRT组合的

来源:De1CTF2019的babyrsa(部分)

1
2
3
4
5
6
7
p  = 
q1 =
q2 = 
c1 = 
c2 = 
assert(c1==pow(flag,e1,(p-1)*(q1-1))
assert(c2==pow(flag,e2,(p-1)*(q2-1))

经测试gcd(e1,p-1) = 14,所以私钥d不唯一

但是我们可以通过上面的方法把m**14求出来

1
2
3
4
5
6
7
8
e1 = e1 // tmp
e2 = e2 // tmp

d1 = gmpy2.invert(e1,phi1)
d2 = gmpy2.invert(e2,phi2)

c1 = gmpy2.powmod(c1,d1,p*q1)
c2 = gmpy2.powmod(c2,d2,p*q2)

如果这里的指数是2或者3,可以考虑本文的第二种方法

可是由于m很大且指数也不小,所以必须考虑其他方法

求不出d的主要原因就是 gcd(e1,p-1) = gcd(e2,p-1)

于是把原式拆分,把不互素的去除

可以得到两个式子:

  • c1 = m**14 mod q1
  • c2 = m**14 mod q2

这里可以用CRT求得m**14的一个特解

即有:

1
c = m**14 mod q1*q2

原问题被转化为一个新的rsa问题

对于这个新的问题的gcd(e,phi) = 2,可以使用本文第一种方法解决

可以参考:https://www.anquanke.com/post/id/164575

4.论文题

有限域开根:https://eprint.iacr.org/2013/117.pdf

已知一个根,求出剩下的根:https://crypto.stackexchange.com/questions/63614/finding-the-n-th-root-of-unity-in-a-finite-field

1
2
3
4
5
6
7
8
9
10
e = 0x1337
p = 
q = 
n = p * q

assert(flag.startswith('NCTF'))
m = int.from_bytes(flag.encode(), 'big')
assert(m.bit_length() > 1337)

c = pow(m, e, n)

题目难点在于gcd(e,p-1) = gcd(e,q-1) = e

可以通过第一个论文中提到的方法开得一个根,再用第二个提到的方法,求得剩下的根

再用crt组合即可

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
75
76
77
78
79
80
81
c = pow(m,e,p)
#e = 1801,被p-1整除。

import random
import math
import libnum
import time
from Crypto.Util.number import bytes_to_long,long_to_bytes
p = 0
#设置模数
def GF(a):
    global p
    p = a
#乘法取模
def g(a,b):
    global p
    return pow(a,b,p)


def AMM(x,e,p):
    GF(p)
    y = random.randint(1, p-1)
    while g(y, (p-1)//e) == 1:
        y = random.randint(1, p-1)
        print(y)
    print("find")
    #p-1 = e^t*s
    t = 1
    s = 0
    while p % e == 0:
        t += 1
        print(t)
    s = p // (e**t)
    print('e',e)
    print('p',p)
    print('s',s)
    print('t',t)
    # s|ralpha-1
    k = 1    
    while((s * k + 1) % e != 0):
        k += 1
    alpha = (s * k + 1) // e
    #计算a = y^s b = x^s h =1
    #h为e次非剩余部分的积
    a = g(y, (e ** (t - 1) ) * s)
    b = g(x, e * alpha - 1)
    c = g(y, s)
    h = 1
    #
    for i in range(1, t-1):
        d = g(b,e**(t-1-i))
        if d == 1:
            j = 0
        else:
            j = -math.log(d,a)
        b = b * (g(g(c, e), j))
        h = h * g(c, j)
        c = g(c, e)
    #return (g(x, alpha * h)) % p
    root = (g(x, alpha * h)) % p
    roots = set()
    for i in range(e):
        mp2 = root * g(a,i) %p
        assert(g(mp2, e) == x)
        roots.add(mp2)
    return roots
def check(m):
    if 'flag' in m:
        print(m)
        return True
    else:
        return False

    e = 1801
c = 821562155714228494350968286343241874202753771452745916900616612053610190986294297934462409534126095213198464996196364868528238538372119009517541428785632007137206972918081643841690069171088425923887930051635578719252415693144672179185417101210954906623326286804995637775062840407550493095027500638719998
p = 19897846550210846565807788524492364050901480736489979129040638436463635149815428186161001280958415730930156556581274966745574164608778242980049611665461488306439665507971670397595035647317930606555771720849158745264269952668944940061576328219674721623208805067371087817766416300084129945316973502412996143
mps = AMM(c,e,p)
for mpp in mps:
        solution = str(long_to_bytes(mpp))
        if check(solution):
           print(solution)