P13. dp,dq

P13.dp,dq

出题脚本

#coding:utf-8
import random
import base64
import hashlib
import string
import libnum

def put_flag():
    # 字符串列表
    a = string.printable
    flag = ""
    for i in range(10):
        flag += a[random.randint(0, 99)]
    flag = r"flag{%s}"%(hashlib.md5(flag.encode()).hexdigest())
    print(flag)
    return flag
#生成素数
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
e=65537
n=p*q
phi_n=(p-1)*(q-1)
d=libnum.invmod(e,phi_n)
dp=d%(p-1)
dq=d%(q-1)
m=put_flag()
m=libnum.s2n(m)
n=p*q
c=pow(m,e,n)

print("p=",p)
print("q=",q)
print("dq=",dq)
print("dp=",dp)
print("c=",c)

解题脚本

# coding=utf-8
import gmpy2
import libnum

def decrypt(dp,dq,p,q,c):
    InvQ = gmpy2.invert(q, p)
    mp = pow(c, dp, p)
    mq = pow(c, dq, q)
    m = (((mp-mq)*InvQ) % p)*q+mq
    print(libnum.n2s(int(m)).decode())

p= 
q= 
dq= 
dp= 
c= 

decrypt(dp,dq,p,q,c)

题目解析

c = m^e mod n

m = c^d mod n

ϕ(n)= (p−1)∗(q−1)

d∗e≡ 1 mod ϕ(n)

dp= d mod (p−1)

dq= d mod (q−1)

首先根据

m=c^d mod n

gcd(p,q)=1
n=p∗q

利用中国剩余定理,得：
m1=c^d mod p
m2=c^d mod q

m=c^d mod n
m=c^d+k∗n

n=p∗q
m=c^d+p∗q∗k


同时取余q和p

m1≡c^d mod q
m2≡c^d mod p

c^d=kp+m1


式1带入式2
m2≡(kp+m1) mod q

等式两边同时减去m1,
(m2−m1)≡kp mod q

gcd(p,q)=1

所以可以求p的逆元，得到
(m2−m1)∗p1≡k mod q

得到如下两个式子
k≡(m2−m1)∗p1mod q
c^d=kp+m1
m≡c^d mod n


上下两个式子合并

c^d = ((m2−m1)∗p1 mod q)p+m1
m ≡ c^d mod n

最后可以有

m≡(((m2−m1)∗p1 mod q)p+m1) mod n

只剩最后一步了

m1≡cd mod q
m2≡cd mod p

m1和m2怎么求

d≡dp mod (p−1)
d≡dq mod (q−1)

那么分别带入

m1≡cdq mod (q−1) mod q
m2≡cdp mod (p−1) mod p

费马小定理即假如p是质数，且gcd(a,p)=1
a(p−1)≡1 mod p

所以如果我们有等式

d=dp+k∗(p−1)

直接带入
m2≡c^dp+k∗(p−1) mod p

这里的指数，我们拆开，为
m2≡c^dp∗ck∗(p−1) mod p

ck∗(p−1)≡1 mod p

因为p是大素数，显然和c互素所以可以直接得到
m2≡cdp mod p

那么m1根据对称性也可以同理得到

m1≡cdq mod q

故此，我们现在拥有了所有条件，下面归纳一下为

m1≡cdq mod q
m2≡cdp mod p
m≡(((m2−m1)∗p1 mod q)p+m1) mod n