分类目录归档：密码学与编码 Crypto

CTF RSA 高精度整数开根 解一元二次方程

发表评论

做BJDCTF第二届出的RSA题目，需要解高精度整数的一元二次方程，参考着网上写了个Python脚本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def HPSqrt(a,b): #高精度开整数根，a为开几次根，b为要开根的数
    l=0
    r=1
    while(r**a<=b):
        l=r
        r=r*2  
    while(l+1<r):  
        mid=(l+r)//2
        if (mid**a<=b): l=mid
        else: r=mid
    if (l**a<=b): return l
    else: return r

def HPSolve12(a,b,c): #高精度解整数一元二次方程，解RSA用
    key=HPSqrt(2,b*b-4*a*c)
    return ((-b+key)//2//a,(-b-key)//2//a)

a=1
b=-2
c=1
print(HPSolve12(a,b,c)) #将方程整理成ax^2+bx+c=0的形式代入即可

参考资料：高精度Python开根 https://www.luogu.com.cn/blog/wjy666/solution-p2293

CTF Crypto RSA

发表评论

已知质数p,q，公钥（指数）e，求私钥d。
利用欧拉定理解私钥d，利用扩展欧几里得求逆元。
python代码：

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
def CPPDiv(a,b):
    return int(a/b)

def CPPMod(a,b):
    quotient = CPPDiv(a,b)
    return a-b*quotient

def ExGCD(a,b,x,y): # Return GCD,x,y
    if b==0: return a, 1, 0
    d, y, x = ExGCD(b, CPPMod(a,b), y ,x)
    y -= CPPDiv(a,b)*x
    return d, x, y

def ExGCD_Cal(a,b):
    return ExGCD(abs(a),abs(b),0,0)[1:]

def QuickPow(a,b,MOD):
    if b==0: return 1
    result = QuickPow(a,b//2,MOD) % MOD
    result *= result
    if b&1==1: result *= a
    result %= MOD
    return result

def solveRSAd(n,phi,e):
    u, v = ExGCD_Cal(e, phi)
    if v>0:
        u += phi
        v = e-v
    return u

def Main():
    p = int(input("Prime p:"))
    q = int(input("Prime q:"))
    phi = (p-1)*(q-1)
    n = p * q
    print("Mod N: %d" % n)
    e = int(input("Public Key e:"))
    d = solveRSAd(n, phi, e)
    print("Private Key d: %s" % d)

if __name__ == '__main__':
    Main()

已知质数p,q，公钥（指数）e，和密文c，解出私钥d和明文m。

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
def CPPDiv(a,b):
    return int(a/b)

def CPPMod(a,b):
    quotient = CPPDiv(a,b)
    return a-b*quotient

def ExGCD(a,b,x,y): # Return GCD,x,y
    if b==0: return a, 1, 0
    d, y, x = ExGCD(b, CPPMod(a,b), y ,x)
    y -= CPPDiv(a,b)*x
    return d, x, y

def ExGCD_Cal(a,b):
    return ExGCD(abs(a),abs(b),0,0)[1:]

def QuickPow(a,b,MOD):
    if b==0: return 1
    result = QuickPow(a,b//2,MOD) % MOD
    result *= result
    if b&1==1: result *= a
    result %= MOD
    return result

def solveRSAd(n,phi,e):
    u, v = ExGCD_Cal(e, phi)
    if v>0:
        u += phi
        v = e-v
    return u

def Main():
    p = int(input("Prime p:"))
    q = int(input("Prime q:"))
    phi = (p-1)*(q-1)
    n = p * q
    print("Mod N: %d" % n)
    e = int(input("Public Key e:"))
    d = solveRSAd(n, phi, e)
    print("Private Key d: %s" % d)
    c = int(input("Cipher c:"))
    m = pow(c,d,n)
    print("Plain m: %s" % str(hex(m)))
   

if __name__ == '__main__':
    Main()

参考链接：

数论代码总结

洛谷 同余方程


https://www.freebuf.com/sectool/163781.html
还有一本数论概论:)