烟虚境
0%

RSA基础

发表于 更新于

笔者在图书馆敲了一上午的内容，奖励一块榴莲披萨！

模运算法则

(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a b) % p = (a % p b % p) % p
a ∧ b % p = ((a % p) ∧ b) % p

结合律
((a + b) % p + c) = (a + (b + c) % p) % p
((a b) % p c) = (a (b c) % p) % p

交换律
(a + b) % p = (b + a) % p
(a b) % p = (b a) % p

分配律
(a + b) % p = (a % p + b % p) % p
((a + b) % p c) % p = ((a c) % p + (b * c) % p)

重要定理
若 a ≡ b (mod p)，则对于任意的 c，都有 (a + c) ≡ (b + c) (mod p)
若 a ≡ b (mod p)，则对于任意的 c，都有 (a c) ≡ (b c) (mod p)
若 a ≡ b (mod p)，c ≡ d (mod p)，则
(a + c) ≡ (b + d) (mod p)
(a - c) ≡ (b - d) (mod p)
(a c) ≡ (b d) (mod p)
(a / c) ≡ (b / d) (mod p)

RSA基础

(以下等号都是同余的意思)

加密 c=m^e(mod n)

解密m=c^d (mod n)

n=p*q

phi_n=(p-1)(q-1)

ed=1(mod phi_n)

接下来来证明解密过程的正确性

c^d=m^(ed)(mod n) 1式

ed=1+k*phi_n 2式

c^d=m^(1+k*phi_n)(mod n) 2代1

​ =m m^(kphi_n) (mod n)

​ ={ m(mod n)*(m^phi_n)^k(mod n) }(mod n)

根据模运算和欧拉定理

c^d=m(mod n)

1
2
3
4
5
6
7
#随机生成flag脚本
for i in range(10):
    flag = ""
    for j in range(10):
        flag += a[random.randint(0, 99)]
    flag = hashlib.md5(flag.encode()).hexdigest()
    print(f"flag{" + flag + "}")

题目一：已知n,e,d,c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#加密
import gmpy2
import libnum

p=libnum.gernerate_prime(1024)
q=libnum.gernerate_prime(1024)
n=p*q
e=65537
phi_n=(p-1)(q-1)
d=gmpy2.invert(e,phi_n)
m=libnum.s2n(flag)
c=pow(m,e,n)
print("n=",n)
print("e=",e)
print("d=",d)
print("c=",c)
1
2
3
4
5
6
7
#解密
import libnum
n=...
d=...
c=...
m=pow(c,d,n)
print(libnum.n2s(m))

题目2：已知n,e,c(n能分解的情况下)

1
2
3
4
5
6
7
8
9
10
11
12
13
#加密
import gmpy2
import libnum

p=libnum.gernerate_prime(1024)
q=gmpy2.next_prime(1024)
n=p*q
e=65537
m=libnum.s2n(flag)
c=pow(m,e,n)
print("n=",n)
print("e=",e)
print("c=",c)

要求d，需知phi_n；要知phi_n,需知p,q,

使用yafu分解得到p,q

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#解密
import gmpy2
import libnum

n=...
p=...
q=...
e=...
c=...
assert n=p*q
phi_n=(p-1)(q-1)
d=gmpy2.invert(e,phi_n)
m=pow(c,d,n)
print(libnum.n2s(int(m))

题目3：给出不同的e，但n,c相同（共模攻击）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#加密
import gmpy2
import libnum

p=libnum.gernerate_prime(1024)
q=libnum.gernerate_prime(1024)
n=p*q
e1=2333
e2=23333
m=libnum.s2n(flag)
c1=pow(m,e1,n)
c2=pow(m,e2,n)
print("n=",n)
print("e1=",e1)
print("e2=",e2)
print("c1=",c1)
print("c2=",c2)

c1=m^e1%n

c2=m^e2%n

想办法得到m

令

c1^s =m^(e1*s)%n

c2^t=m^(e2*t)%n

m^(e1s+e2t)=(c1^s*c2^t )%n

根据扩展欧几里德算法

对于不完全为 0 的整数 (a, b), gcd(a, b) 表示 (a, b) 的最大公约数。

那么一定存在整数 (x, y) 使得 gcd(a, b) = ax + by

得到s,t

1
2
3
4
5
6
7
8
9
10
11
12
#解密
import gmpy2
import libnum

n=...
e1=...
e2=...
c1=...
c2=...
s,s1,s2=gmpy2.gcdexd(e1,e2)
m=(pow(c1,s1,n)*pow(c2,s2,n)%n)
print(libnum.n2s(int(m))

题目4：给出n,e,c，但e的值较小，可直接爆破（低加密指数攻击）

如果 ( e = 3 )，且 ( m^e < n )，( c ) 开 3 次根式，得到 ( m )。

如果 ( e = 3 )，且 ( m^e > n )，那么设 ( k )，有：
[ c = m^e + kn ]

爆破 ( k )，如果 ( c - kn ) 能开三次根式，得到 ( m )。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#解密
import gmpy2
import libnum

n=...
e=...
c=...
def exp(n,e,c):
    k=0
    while 1:
        m1=k*n+c
        m,t=gmpy2.iroot(m1,e)
        if t:
            print(m)
            print(libnum.n2s(int(m)))
            break
        k+=1

题目5：给出不同的n,c，但m,e相同且e较小（低加密指数广播攻击）

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
#加密
import gmpy2
import libnum


p=libnum.gernerate_prime(1024)
q=libnum.gernerate_prime(1024)
n1=p*q

p=libnum.gernerate_prime(1024)
q=libnum.gernerate_prime(1024)
n2=p*q

p=libnum.gernerate_prime(1024)
q=libnum.gernerate_prime(1024)
n3=p*q
while 1:
    e=random.randint(10,20)
    if gmpy2.is_prime(e):
        break
m=libnum.s2n(flag)
c1=pow(m,e,n1)
c2=pow(m,e,n2)
c3=pow(m,e,n3)
print("n1=",n1)
print("n2=",n2)
print("n3=",n3)
print("c1=",c1)
print("c2=",c2)
print("c3=",c3)

根据前面学习的数论知识，可以使用中国剩余定理 解出m^e,然后进行开方

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
#解密
import gmpy2
import libnum

n1=...
n2=...
n3=...
c1=...
c2=...
c3=...
def GCRT(m, a):
    assert (len(m) == len(a))
    curm, cura = m[0], a[0]
    for m, a in zip(m[1:], a[1:]):
        d = gmpy2.gcd(curm, m)
        c = a - cura
        assert (c % d == 0)
        K = c // d * gmpy2.invert(curm // d, m // d)
        cura += curm * K
        curm = curm * m // d
    return cura % curm
n=[n1,n2,n3]
c=[c1,c2,c3]
mm= GCRT(n,c)
for e in range(10,20):
    m,t=gmpy2.iroot(mm,e)
    if t:
        print(m)
        print(libnum.n2s(int(m)))

题目6：给出不同的n,c，但m,e相同且e较大（n不互素）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#加密
import gmpy2
import libnum

flag="flag{"+str(uuid.uuid4())+"}"
m=libnum.s2n(flag)
p=libnum.gernerate_prime(1024)
q1=libnum.gernerate_prime(1024)
q2=libnum.gernerate_prime(1024)
n1=p*q1
n2=p*q2
e=65537
c1=pow(m,e,n1)
c2=pow(m,e,n2)
print("n1=",n1)
print("n2=",n2)
print("c1=",c1)
print("c2=",c2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#解密
import gmpy2
import libnum

n1=...
n2=...
c1=...
c2=...
e=65537
p=gcd(n1,n2)
q1=n1//p
phi_n=(p-1)*(q1-1)
d=gmpy2.invert(e,phi_n)
m=pow(c1,d,n1)
print(libnum.n2s(int(m)))
变形（将flag分成前后两段分别算m)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#加密
import gmpy2
import libnum
import uuid

flag="flag{"+str(uuid.uuid4())+"}"
m1=libnum.s2n(flag[:21])
m2=libnum.s2n(flag[21:])
p=libnum.gernerate_prime(1024)
q1=libnum.gernerate_prime(1024)
q2=libnum.gernerate_prime(1024)
n1=p*q1
n2=p*q2
e=65537
c1=pow(m1,e,n1)
c2=pow(m2,e,n2)
print("n1=",n1)
print("n2=",n2)
print("c1=",c1)
print("c2=",c2)

上一个脚本多走一步，得到m1,m2，拼起来

题目7：已知n,e,c,dp(dp泄露)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#加密
import gmpy2
import libnum
import uuid

flag="flag{"+str(uuid.uuid4())+"}"
m=libnum.s2n(flag)
p=libnum.gernerate_prime(1024)
q=libnum.gernerate_prime(1024)
n=p*q
e=65537
phi_n=(p-1)(q-1)
d=gmpy2.invert(e,phi_n)
dp=d%(p-1)
print("n=",n)
print("e=",e)
print("c=",c)
print("dp=",dp)

dp=d+k*(p-1)

edp=e d+e k (p-1)

​ =1+e*k1(p-1) (mod phi_n)

e dp-1=ek1(p-1)+k *phi_n

phi_n=(p-1)(q-1)

e dp-1=ek1(p-1)+k (p-1)(q-1)=(ek1+k(q-1))(p-1)=k2 (p-1)

又因为dp<p-1(dp=d%(p-1)是其余数)

所以e>k2,即k2<65537

遍历e找到k2然后就能算出p

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#解密
import gmpy2
import libnum

n=...
e=...
c=...
dp=...

for i in range(1,65535):
    p=(dp*e-1)//i+1
    if n%p==0:
        q=n//p
        break

print(p)
print(q)

phi_n=(p-1)*(q-1)
d=gmpy2.invert(e,phi_n)
m=pow(c,d,n)
print(libnum.n2s(int(m)))

题目8：给出p,q,c,dp,dq(dp,dq泄露)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#加密
import gmpy2
import libnum
import uuid

flag="flag{"+str(uuid.uuid4())+"}"
m=libnum.s2n(flag)
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
e=65537
n=p*q
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
dp=d%(p-1)
dq=d%(q-1)
c=pow(m,e,n)
print("p=",p)
print("q=",q)
print("c=",c)
print("dp=",dp)
print("dq=",dq)

dp=d%(p-1)

dp=d-k(p-1) d=dp+k (p-1)

m=c^d%n

m=c^d+kpq

m%p=(c^d%p+kpq%p)%p

m=c^d%p(当m<p时)

m=c^d+kp=c^(dp+k *(p-1))+kp

m%p=(c^dp%pc^k (p-1)%p)%p

m=c^dp%p(m<p时)

1
2
3
4
5
6
7
8
9
10
11
12
#解密
import gmpy2
import libnum 

p=...
q=...
c=...
dp=...
dq=...
m=pow(c,dp,p)
m=pow(c,dq,q)
print(libnum.n2s(int(m)))

题目9：已知n,e,c,p,且n是p的r次方

根据欧拉函数

若n=p^r

phi_n=p^r-p^(r-1)

证明如下

phi_n代表从1到n中与n互质的素数的个数

在1到p^r中，1和p是其唯二素公因子

那么有1p,2p,3p,…..p^(r-1)p与其不互质

一共有p^r个数，减去着p^(r-1)个数就是最终phi_n的值

1
2
3
4
5
6
7
8
9
10
11
12
13
#解密
import gmpy2
import libnum

n=...
e=...
c=...
p=...
#假设r=3
phi_n=(p-1)*p**2
d=gmpy2.inverrt(t1,phi_n)
m=pow(c,d,n)
print(libnum,n2s(int(m)))
变形(n=p^r*q)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#解密
import gmpy2
import libnum

n=...
e=...
c=...
p=...
q=n//p
#假设r=3
phi_n=(p-1)*p**2*(q-1)
d=gmpy2.inverrt(t1,phi_n)
m=pow(c,d,n)
print(libnum,n2s(int(m)))

题目10：n分解3个素数(p和q能分解出来)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#加密
import libnum
import uuid
import gmpy2

flag="flag{"+str(uuid.uuid4())+"}"
m=libnum.s2n(flag)
p=libnum.generate_prime(512)
q=gmpy2.next_prime(p)
r=libnum.generate_prime(512)
n=p*q*r
e=65537
c=pow(m,e,n)
print("r=",r)
print("n=",n)
print("e=",e)
print("c=",c)

n=pq r

p*q=n//r

phi_n=(p-1)(q-1)(r-1)

由此可继续

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#解密
import gmpy2
import libnum

r=...
n=...
pq=n//r
print("pq=",pq)
#用yafu分解得到p,q
p=...
q=...
phi_n=(p-1)(q-1)(r-1)
d=gmpy2.inverrt(t1,phi_n)
m=pow(c,d,n)
print(libnum,n2s(int(m)))

题目11:e和phi_n不互素(就求不出e在模n下的逆元d了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#加密
import gmpy2
import libnum
import random
import uuid

flag="flag{"+str(uuid.uuid4())+"}"
m=libnum.s2n(flag)

while 1:
    e = random.randint(100,1000)
    p=libnum.generate_prime(1024)
    q=libnum.generate_prime(1024)
    phi_n=(p-1)*(q-1)
    t=gmpy2.gcd(e,phi_n)
    if gmpy2.invert(e // t, phi_n) and t != 1:
        break
n=p*q
c=pow(m,e,n)
print("p=",p)
print("q=",q)
print("e=",e)
print("c=",c)

我们可以求出一个与phi_n互素的公钥t1，然后转换成原来的题目

令t=gcd(e,phi_n)

t1=e//t

c=m^e=m^(t*t1)=(m^t)^t1%n

此时m^t进行开方后就能得到m了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#解密
import gmpy2
import libnum

p=...
q=...
e=...
c=...
phi_n=(p-1)*(q-1)
t=gcd(e,phi_n)
t1=e//t
d=gmpy2.inverrt(t1,phi_n)
m1=pow(c,d,n)
s,m=gmpy.iroot(m1,t)
print(s,m)
print(libnum.n2s(int(m)))

题目12：n,c不互素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#加密
import libnum
import gmpy2
import uuid

flag="flag{"+str(uuid.uuid4())+"}"  
m=libnum.s2n(flag)  

p=libnum.generate_prime(1024)  
q=libnum.generate_prime(1024)  
n=p*q  
e=65537  

c=pow(m*p,e,n)   
print("n=", n)  
print("c=", c)  
print("e=", e)

c=pow(m*p,e,n)

c=(m*p)^e-kpq

c%p=0

p=gcd(c,n)

q=n//p

然后解密即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#解密
import libnum
import gmpy2

n=...
c=...
e=...
p=gcd(n,c)
q=n//p
phi_n=(p-1)*(q-1)
d=gmpy2.invert(e,phi_n)
m=pow(c,d,n)
m1=m//p
print(libnum.s2n(int(m1)))

https://www.bilibili.com/read/readlist/rl472724

-------------本文结束感谢您的阅读-------------