RSA(持续补充)

CTF crypto
CTF
发布日期:   2023-11-01
更新日期:   2023-11-01
文章字数:   4.1k
阅读时长:   22 分
阅读次数:  

一.概述

1.介绍

明文 m：就是待加密的文本，一般也就是我们的flag。

密文 C：加密完成后的密文，一般题目会给你，我们要做的就是根据密文解密出明文。

公钥 e（加密钥）：用来加密的密钥，是一个整数，是公开的。

两个大素数 p,q：RSA加密的关键部分，一般不会告诉你。我们选取两个大素数并计算它们的乘积，得到n=p*q。后面会用p,q,n来加密解密。由于p,q非常大，想要对n进行因式分解得到p，q非常困难，这也确保了RSA的安全性。

私钥 d（解密钥）：用来解密，一般不会告诉你，d满足e*d mod (p-1)(q-1)=1，所以我们只要知道e和p,q就可以把d算出来。

加密过程：
image

解密过程：
image

以上就是一个常规RSA算法的组成部分。通过上面的内容我们可以知道要想解密一段密文，我们需要c,d,n三个值。其中c我们是知道的，而n和d都可以通过p,q,e算出来，e我们一般也是知道的，也就是说常规的rsa题目我们的解题思路就是想想怎样把p和q求出来。并以此进行解密。

二.工具

1.python

python是必备工具，脚本需要
要求的库包括但不限于：gmpy2、pycryptodome、libnum

2.分解大素数n

1)在线因式分解

http://www.factordb.com/

2)yafu

n较小的时候 yafu-x64 factor(n)
n复制到txt文件中再分解，用于n过长的情况yafu-x64 "factor(@)" -batchfile 1.txt 注意txt文件最后一定要回车一下

3)费马分解(p,q接近)

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
def isqrt(n):
  x = n
  y = (x + n // x) // 2
  while y < x:
    x = y
    y = (x + n // x) // 2
  return x

def fermat(n, verbose=True):
    a = isqrt(n) # int(ceil(n**0.5))
    b2 = a*a - n
    b = isqrt(n) # int(b2**0.5)
    count = 0
    while b*b != b2:
        # if verbose:
        #     print('Trying: a=%s b2=%s b=%s' % (a, b2, b))
        a = a + 1
        b2 = a*a - n
        b = isqrt(b2) # int(b2**0.5)
        count += 1
    p=a+b
    q=a-b
    assert n == p * q
    # print('a=',a)
    # print('b=',b)
    # print('p=',p)
    # print('q=',q)
    # print('pq=',p*q)
    return p, q
fermat(n)

4)短除法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
"""短除法-1
从i为2开始枚举，一直枚举到，
一旦n % i == 0成立，则i为n的因子，
然后进行n //= i使运行速度加快并使i为质数才可能有n % i == 0。
 
复杂度：0（n^1/2）
适用范围：n: 2-10^16
"""
def factorization(n):
    i = 2
    ret = []
    while i * i <= n:
        while n % i == 0:
            ret.append(i)
            n //= i
        i += 1
    if n > 1:
        ret.append(n)
    return (ret)
 
if __name__ == '__main__':
    print(factorization(int(input())))

4)短除法2

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
"""短除法2
我们可以打表出2到n^1/2之间的质数再进行试除，这样在解决多个数的质因数分解时才会免除大部分合数的影响。
用素数筛进行打表复杂度为O(n)，我们也只需要从2到n^1/2打表到即可。
 
复杂度：0（n^1/2）
适用范围：n 2-10^12
 
"""
pri = []
MX = int(1e6)
isprime = [True] * MX
def init():
    global a, MX
    for i in range(2, MX):
        if isprime[i]:
            pri.append(i)
            for j in range(i + i, MX, i):
                isprime[j] = False
 
 
def factorization(n):
    global pri
    ret = []
    for i in pri:
        if i * i > n:
            break
        while n % i == 0:
            ret.append(i)
            n //= i
    ret.append(n)
    return (ret)
 
 
 
if __name__ == '__main__':
    init()
    print(factorization(int(input())))

5)Miller-Rabin素性测试和离散对数Pollard_rho分解

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
82
83
84
85
86
87
88
89
90
91
92
93
94
"""
用Miller-Rabin素性测试和离散对数Pollard_rho算法进行大数因数分解：
复杂度：0(n^1/4)
适用范围：n 2-10^33
 
"""
import random
from math import log, log10
from collections import Counter
 
def gcd(x, y):
    return x if y == 0 else gcd(y, x % y)
 
def fpow(a, x, n):
    ans = 1
    while x > 0:
        if x & 1:
            ans = ans * a % n
        a = a * a % n
        x >>= 1
    return ans
 
# there change the times of Rabin-Miller
TIMES = 10
def is_prime(n):
    def check(a, n, x, t):
        ret = fpow(a, x, n)
        last = ret
        for i in range(0, t):
            ret = ret * ret % n
            if ret == 1 and last != 1 and last != n - 1:
                return True
            last = ret
        if ret != 1:
            return True
        return False
 
    if not isinstance(n, int):
        raise TypeError(str(n) + ' is not an integer!')
    if n <= 0:
        raise ValueError('%d <= 0' % n)
    if n in {2, 3, 5, 7, 11}:
        return True
    for i in {2, 3, 5, 7, 11}:
        if n % i == 0:
            return False
    x = n - 1
    t = 0
    while not x & 1:
        x >>= 1
        t += 1
    for i in range(0, TIMES):
        a = random.randint(1, n - 2)
        if check(a, n, x, t):
            return False
    return True
 
def pollard_rho_2(n, c):
    x = random.randint(0, n)
    i, k, y = 1, 2, x
    while True:
        i += 1
        x = (x * x) % n + c
        d = gcd(y - x, n)
        if d != 1 and d != n:
            return d
        if y == x:
            return n
        if i == k:
            y = x
            k <<= 1
 
def pollard_rho_1(n):
    if not isinstance(n, int):
        raise TypeError(str(n) + ' is not an integer!')
    if n == 1:
        return None
    if is_prime(n):
        return [n]
    ans = []
    p = n
    while p >= n:
        p = pollard_rho_2(p, random.randint(1, n - 1))
    ans.extend(pollard_rho_1(p))
    ans.extend(pollard_rho_1(n // p))
    return ans
 
def factorization(n):
    return Counter(pollard_rho_1(n))
 
if __name__ == '__main__':
    n = int(input())
    print('len:', len(str(n)))
    print(factorization(n))

6)d很小，e很大，使用脚本出d，不用分解n

rsa-wiener-attack-master

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
import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator

def hack_RSA(e,n):
    '''
    Finds d knowing (e,n)
    applying the Wiener continued fraction attack
    '''
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)
    
    for (k,d) in convergents:
        
        #check if d is actually the key
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if(discr>=0):
                t = Arithmetic.is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    print("Hacked!")
                    return d

def test_hack_RSA():
        e=8614531087131806536072176126608505396485998912193090420094510792595101158240453985055053653848556325011409922394711124558383619830290017950912353027270400567568622816245822324422993074690183971093882640779808546479195604743230137113293752897968332220989640710311998150108315298333817030634179487075421403617790823560886688860928133117536724977888683732478708628314857313700596522339509581915323452695136877802816003353853220986492007970183551041303875958750496892867954477510966708935358534322867404860267180294538231734184176727805289746004999969923736528783436876728104351783351879340959568183101515294393048651825

        n=19873634983456087520110552277450497529248494581902299327237268030756398057752510103012336452522030173329321726779935832106030157682672262548076895370443461558851584951681093787821035488952691034250115440441807557595256984719995983158595843451037546929918777883675020571945533922321514120075488490479009468943286990002735169371404973284096869826357659027627815888558391520276866122370551115223282637855894202170474955274129276356625364663165723431215981184996513023372433862053624792195361271141451880123090158644095287045862204954829998614717677163841391272754122687961264723993880239407106030370047794145123292991433

        hacked_d = hack_RSA(e, n)
        print("hacked_d = ", hacked_d)
        print("-------------------------")
        
if __name__ == "__main__":
    test_hack_RSA()
#修改n,e即可

三.类型

注意：具体类型的具体原理可以上网自行查阅

1.n可以在线或者yafu分解

1.1分解成两个素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import gmpy2
#import libnum
from Crypto.Util.number import long_to_bytes
 
c = 0x6cd55a2bbb49dfd2831e34b76cb5bdfad34418a4be96180b618581e9b6319f86
n = 108539847268573990275234024354672437246525085076605516960320005722741589898641
#n = int("",16)
e = 65537
#e = int("",16)
q = 333360321402603178263879595968004169219
p = 325593180411801742356727264127253758939

phi = (p - 1)*(q - 1)
#d = libnum.invmod(e, phi)   使用libnum库
d = gmpy2.invert(e, phi)   #使用gmoy2库
#d = pow(e, -1, phi)
m = pow(c, d, n)   # m 的十进制形式
flag = long_to_bytes(m)  # m明文
print(flag)  # 结果为 b‘ m ’ 的形式

1.2可以分解成多个素数

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
import gmpy2
from Crypto.Util.number import long_to_bytes
 
n= 17290066070594979571009663381214201320459569851358502368651245514213538229969915658064992558167323586895088933922835353804055772638980251328261
e= 65537
c= 14322038433761655404678393568158537849783589481463521075694802654611048898878605144663750410655734675423328256213114422929994037240752995363595
P1 = 4093178561
P2 = 2804303069
P3 = 3207148519
P4 = 2923072267
P5 = 2338725373
P6 = 2463878387
P7 = 2970591037
P8 = 3654864131
P9 = 2370292207
P10 = 3939901243
P11 = 2706073949
P12 = 4278428893
P13 = 3831680819
P14 = 2794985117
P15 = 2217990919
phi = (P1-1)*(P2-1)*(P3-1)*(P4-1)*(P5-1)*(P6-1)*(P7-1)*(P8-1)*(P9-1)*(P10-1)*(P11-1)*(P12-1)*(P13-1)*(P14-1)*(P15-1)  
d = gmpy2.invert(e, phi)  
m = pow(c, d, n)  
print (long_to_bytes(m))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
原理：
首先我们证明 M^(k(p-1)(q-1)(r-1)+1) mod p=M mod p    ［ 1 ］
1.如果 M 、 p 不互质，那么p 能整除 M, 明显 p也能整除 M^(k(p-1)(q-1)(r-1)+1), 那么： M^(k(p-1)(q-1)(r-1)+1) mod p=M mod p＝0
2.若 p 、 q 互质， 根据欧拉定理 M^Φ (p) mod p=1 ，有
M^(k(p-1)(q-1)(r-1)+1) mod p
=((M)M^k(p-1)(q-1)(r-1)) mod p
=((M)(M^(p-1))^k(q-1)(r-1)) mod p
=((M)(M^Φ(p))^k(q-1)(r-1)) mod p
=(M mod p)*[(M ^Φ(p)) mod p]^k(q-1)(r-1)
=(M mod p)*(1)^k(q-1)(r-1) （根据欧拉定理）
=M mod p
根据［ 1 ］ , 有 [M^(k(p-1)(q-1)(r-1)+1)－M] mod p=0 (2)，
同理，可证明 [M^(k(p-1)(q-1)(r-1)+1)－M] mod q=0（3）
[M^(k(p-1)(q-1)(r-1)+1)－M] mod r=0    (4)
根据［ 2 ］［ 3 ］［ 4 ］知，存在一整数 x 使
[M^(k(p-1)(q-1)(r-1)+1)－M]=(pqr)x=nx
所以 n 能整除 [M^(k(p-1)(q-1)(r-1)+1)－M]
故 M^(k(p-1)(q-1)(r-1)+1) mod n=M^(k准(n)+1) mod n=M
根据 ed=k准(n)+1 （逆元关系）
得 M=^ed mod n=M

2.低加密指数攻击（e很小）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import gmpy2
from Crypto.Util.number import *
 
def de(c, e, n):
    k = 0
    while True:
        m = c + n*k
        result, flag = gmpy2.iroot(m, e)
        if True == flag:
            return result
        k += 1
e= 3
n= 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
c= 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
 
m=de(c,e,n)
print(long_to_bytes(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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#脚本2
'''
题目：
from Crypto.Util.number import getPrime,bytes_to_long

p,q = getPrime(2048),getPrime(2048)
e = 7
n = p*q
m = bytes_to_long(open('flag.txt','rb').read().strip())
c = pow(m,e,n)
print("c = ",c)
print("n = ",n)

# c =  147693154873835354725007152781732424355869776162377337823960431913672366269917723916891506269449726723757821517328874729037838600793748824028829185409932536014732765063216715033843955453706710187792772702199448156372644163429786386035008302836467605094954587157232829525150652611067567669525072625329634860065850520051628272535479197120008981979404760445193750864902244921407742155742716289495581989134730376783828846663464819337418977287363028738701414486788851136608957124505485242331701209645216580641917007780811842757125048746184068597664780265422321550909392419865169775282217442331295071069272774722564587602419768461231775480847018941840911357926330143045826277813722919121117172763493242590521245640828462665947672485094793188432098216701511715232654611338293295459889814699850788048985878279440740712956248569068077253790198036918598519191892836075254345518967666166925163908185663991353344555402397055977817370082929420443034626201745027965444069777059760865359310439815816749939498993014457995041394803598825093836045546578310632172636478575946653375857640993393714607308326474003446154152048840071034349831168612740218034679021240949747357214453636633636662650940968576792518622437627529244515229173

# n =  553409369582823237678532685244026647155180191225879439432235077135813123637186465008813830373646133388592395760175777499266561095087891764348044063111935877931069321764391883899483374576303169645488542398590564148654412004383012178107972880058460460806768779452529433458826925606225797078653905380530651390617109384086518728626571028089036812787671647095695947167204428442727185744172445701874820612799168887428075695751162763647868386879374037826876671079326544820609721731078985096813307183878793033824330869698508952853770794414757655681370862323768018291030331209143189638496644361618184164228294031490537429556439588954274708598530042700988138862000054458742762198052079867259365645914383561162796796952346445529346145323567650621600171442575319262718389389870407629339714751583360252884338116164466349449862781112019462555743429653595045695696967783338371470032332852204294900011651434678829104876529439166176589508898757122660322523937330848536715937381297551894198974459004139082562228022412335520195652419375915216074658463954339332593244483927157329404652516225481116614815221154229491846087288087715884363786672244655901308480290011237244562251084095684531716327141154558809471185132979704992609461470501119328696999713829

低加密指数攻击：
假设e=3, 公钥中的加密指数e很小，但是模数n很大
有RSA加密公式： C=M^e % n (C密文，M明文)
则：
当M^e < n 时，
C = M^e ，所以对C开方就能得到M

当M^e ＞ n 时，此时用爆破的方法
假设我们　 Ｍ^e / n 的商为 k 余数为C，
则Ｍ^e = kn + C，对K进行爆破，只要k满足 kn + C能够开e次方就可以得明文
'''
'''
#解题
#python3
## -*- coding: utf-8 -*-#
from gmpy2 import iroot
import libnum
e = 7
n = 553409369582823237678532685244026647155180191225879439432235077135813123637186465008813830373646133388592395760175777499266561095087891764348044063111935877931069321764391883899483374576303169645488542398590564148654412004383012178107972880058460460806768779452529433458826925606225797078653905380530651390617109384086518728626571028089036812787671647095695947167204428442727185744172445701874820612799168887428075695751162763647868386879374037826876671079326544820609721731078985096813307183878793033824330869698508952853770794414757655681370862323768018291030331209143189638496644361618184164228294031490537429556439588954274708598530042700988138862000054458742762198052079867259365645914383561162796796952346445529346145323567650621600171442575319262718389389870407629339714751583360252884338116164466349449862781112019462555743429653595045695696967783338371470032332852204294900011651434678829104876529439166176589508898757122660322523937330848536715937381297551894198974459004139082562228022412335520195652419375915216074658463954339332593244483927157329404652516225481116614815221154229491846087288087715884363786672244655901308480290011237244562251084095684531716327141154558809471185132979704992609461470501119328696999713829
c = 147693154873835354725007152781732424355869776162377337823960431913672366269917723916891506269449726723757821517328874729037838600793748824028829185409932536014732765063216715033843955453706710187792772702199448156372644163429786386035008302836467605094954587157232829525150652611067567669525072625329634860065850520051628272535479197120008981979404760445193750864902244921407742155742716289495581989134730376783828846663464819337418977287363028738701414486788851136608957124505485242331701209645216580641917007780811842757125048746184068597664780265422321550909392419865169775282217442331295071069272774722564587602419768461231775480847018941840911357926330143045826277813722919121117172763493242590521245640828462665947672485094793188432098216701511715232654611338293295459889814699850788048985878279440740712956248569068077253790198036918598519191892836075254345518967666166925163908185663991353344555402397055977817370082929420443034626201745027965444069777059760865359310439815816749939498993014457995041394803598825093836045546578310632172636478575946653375857640993393714607308326474003446154152048840071034349831168612740218034679021240949747357214453636633636662650940968576792518622437627529244515229173

k = 0
while 1:
    res = iroot(c+k*n,e)  #c+k*n
    #print(res)
    #res = (mpz(13040004482819713819817340524563023159919305047824600478799740488797710355579494486728991357), True)
    if(res[1] == True):
        print(libnum.n2s(int(res[0]))) #转为字符串
        break
    k=k+1
#b'moectf{SMaLL_3xPon3nt_Mak3_rSa_w3ak!_!lP0iYlJf!M3rux9G9Vf!JoxiMl903lllA}'
'''
from gmpy2 import iroot
import libnum
e = 5
n = 18049146130359556157811138499355569967231668855528566823643376144155931993553424757354835027829037263429007310779886281743425186527415596058004878860570474866413182148724803537036078612785180550377667299555519230603647447077725080756322343538156406080031959768393145744701092093127752647143419553963316375696232038952573236311522683541862835602321038621904842874356522524316864553501304106884213097353522958546518042728628006318129608745487662533959888992223736595503203451378533217004433230837006796341055201266431153548000348148960250455415972226546646460918890401484239320725539304914347952245606818833495867312063

c = 377041108412334062897923100149371833160065752130578483588828849399791858197434981428466047315212724764223394695011882740933537996983126187094472520344493047769519118482187945467176598341785927269390299847888131061799861412055502165865052720513992259109503509827127768615772091500352075827289290029872935215672798059068944088543667111296361405639896493856695176145088430237388172420390881291650155157688737470414069130558367036786376549227175617218017578125

k = 0
while 1:
    res = iroot(c+k*n,e)  #c+k*n
    #print(res)
    #res = (mpz(13040004482819713819817340524563023159919305047824600478799740488797710355579494486728991357), True)
    if(res[1] == True):
        print(libnum.n2s(int(res[0]))) #转为字符串
        break
    k=k+1

3.公因数攻击（多组n,c;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
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
'''
https://blog.csdn.net/shuaicenglou3032/article/details/119930783
with open("flag.txt","rb") as f:
    flag = f.read().strip()

m = int.from_bytes(flag, "big")
e = 65537

from Crypto.Util.number import getPrime

for x in range(10):
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    c = pow(m, e, n)

    print("n =", n)
    print("c =", c)


'''
'''
n = 17524722204224696445172535263975543817720644608816706978363749891469511686943372362091928951563219068859089058278944528021615923888948698587206920445508493551162845371086030869059282352535451058203615402089133135136481314666971507135484450966505425514285114192275051972496161810571035753943880190780759479521486741046704043699838021850105638224212696697865987677760179564370167062037563913329993433080123575434871852732981112883423565015771421868680113407260917902892944119552200927337996135278491046562185003012971570532979090484837684759828977460570826320870379601193678304983534424368152743368343335213808684523217
c = 6870605439714128574950893771863182370595667973241984289208050776870220326525943524507319708560433091378319367164606150977103661770065561661544375425887970907060665421562712515902428061727268441585629591525591001533188276465911918724808701356962871139957343861919730086334623932624184172272488406793955068827527130338853980609365042071290967556159598511667974987218999253443575482949258292953639729393456515185185102248985930422080581185292420347510600574229080211050520146551505605537486989306457793451086767402197128573781597156939709237045132856159368959981648969874765462190363842275826077556314448408825308218451
n = 24974121071274650888046048586598797033399902532613815354986756278905133499432183463847175542164798764762683121930786715931063152122056911933710481566265603626437742951648885379847799327315791800670175616973945640322985175516271373004547752061826574576722667907302681961850865961386200909397231865804894418194711076667760169256682834206788730947602211228930301853348503098156592000286467190760378847541148772869356389938999094673945092387627113807899212568399028514283219850734634544982646070106811651490010946670117927664594365986238107951837041859682547029079035013475238052160645871718246031144694712586073789250183
c = 10324627733161143472233272675096997859064721978612320424254305978486200326061730105384511258706433940176741256952824288120499229240005823611541292676234913505775165761543820764046537413943393325463602612485849366939102550336256797820440347815027443410399157963547486098366749815425187247171697678576246606105486928212486117878157055321965270364583625270716186820068538749425299073309429589410882809098930213978117176627031795312102177342499674234163614021182116065492884880492891668658240362567156235958605768725892407536211503981819707919444725863397622629226309480836486427388484176463279384813974310500625102568341
n = 14215826065753265334521416948225868542990756976323308408298887797364519400310818641526401662106853573185085731682502059761982246604277475488691297554851873224516934619888327644352138127883043558424300092247604877819821625587944308487310522092440517150600171819145803937177931473336108429889165189521078678397694303305705260759351843006130968234071638035667854938070597400634242396852782331461576526836227336952718230741560369621645218729592233657856104560425642219241082727756696967324334634822771842625681505869025740662258929200756109704988223034840699133778958569054445520305361142302393767439478256174414187983763
c = 415916446053083522663299405080903121619846594209033663622616979372099135281363175464579440520262612010099820951944229484417996994283898028928384268216113118778734726335389504987546718739928112684600918108591759061734340607527889972020273454098314620790710425294297542021830654957828983606433731988998097351888879368160881316237557097381718444193741788664735559392675419489952796677690968481917700683813252460912749931286739585465657312416977086336732056497161860235343155953578618273940135486362350057858779130960380833359506761436212727289297656191243565734621757889931250689354508999144817518599291078968866323093
n = 12221355905532691305226996552124162033756814028292708728711809229588190407700199452617060657420166395065565154239801465361510672853972152857415394695376825120759202857555325904640144375262531345320714166285999668052224661520834318497234299585219832943519644095197479639328120838919035625832361810964127485907587199925564724081163804724975965691571850962714258888527902920462746795712011579424322515292865504642938090200503979483095345893697972170153990274670257331483858538617460680462369680572833191232126527727222302641204529110948993583190295067970240051042000918629138767209918572311469915774910003970381965123241
c = 2248834602646305164283014556051672824689884721514190813323189875541899566338153534858709617544459297836048770439230174669883719627734394673012731609952869246171300132019334542245094425654362711870373095782083791160029789553806741967408922001051006100049326921742208757147339981269528740944842177729701945606827918253016001436218891580980192743564642120923356793292885805519110411357830040053435569937296612987581482128241218218550319154933831743819546558930918761162723110000328532730751591375727881221199739397698390594797621758011191224528339478784930214820615602510460640307707682865125229937141010351138099874025
n = 18152103454920389919231636321286527841833809319334215885641536161086810144890443857211776387914779781628740172079478910188540146498426564211851629962338413488555121865779016981727229209606498886170396500155102635962395243364899026418106378234307821492609778555173516000309435730752571818439328803899462791834490025768785383592935046996428331508608555503567191807692523852530836008436655164751054189301721070209363416058642811329040202582026786024825518381761299547703962502636888833428457116986351812252188468878701301184044948733274488264320930936362549028124581962244201377136969591119942276742760215403738913067567
c = 2797812094994121597295362327809389195134238119144547570610194659000554967367804835006774413888965325870488368112707535584687083342412367127561646136089638402907513075405746055834487062923240856950047936297155455745928810738711368950139327254040579266046642851362228893522740216519732851152162928545416236075387903789535000820423985522550638100049857678600662008021574841083416323980817348573062083159710189689337626277009675683473560325178417766400002763719953723259300977655801234386662217462862844994462505601804422871991694828697337752697234180117437785537788728412520613916334045368736691714704501962513954509705
n = 22877887459293720334652698748191453972019668578065068224653972884599636421200068659750242304040301306798039254241668648594556654589309801728248683586229288074709849246660525799452637187132633064172425677552176203292787732404537215347782229753837476655088638984496409603054524994383358547132112778403912563916886533181616856401929346567686400616307916690806467019665390260267596320840786982457521423178851498130935577260638269429250197050326097193841333205073650802709022947551398142692735680419453533128176592587955634333425401930362881423044363132586170013458300714163531162544301477356808388416864173949089028317961
c = 12271947322974809255127222556723394446467844330408506340843897575503534175121932185624776713618037572593449207329510171212097269297133492090526270770286000839978630002819714376964416081198925899119135271459404333829811516667576167576916805217016117373027245648473458331936273975110163065432285322832123169216976420362833557809289561705091817949915218278430834098156335989014645979633658818904753942786129126233956314517292746008579152368541316795082120147520597254020266752859205131887527661767589367756335766220841483940854397440079467053684289006956034944336788288196391829411432383541473132962783883758561108297747
n = 19844333358004073542783728196775487079202832688982038135532362073659058674903791697765527614270399097276261983744620537925712167578187109058145015032736796457938148615396547198728652435169126585595701228287449135664667959433491335769206692390262797325133960778920452511673878233190120432257482339068405290918739453464061987163074129048150451046315248186376609350095502130018696275764450248681787926130463463923862832714969425813770847493135627599129546112143050369344208092649256659330284904392961574494907186727388685504929586018639846040474616307662546605623294842316524163106100888851228858194942825157286544846177
c = 9531264751315473345056673937611382755236533664089452852716992791452558274873158812669513178040971923528201631609089069182049526587423864397527252061341857426422965190913745048414029690931254119437249218321954899956104589066479231204536856131403590472063496956452030342299863907499976917750846369802185896519725837163530049157920978007252920334447236842959033879772444475877613295594785710745889554296655932909212643500877218304116451889820444820534937901427158918411546484157737612926382420354101675658160847653151539420222526999426483473829341628599881460824765758346670633385844187252696874025582747177333702736465
n = 16956880944655068255446705024149899655327230949463546092744762226005904114738078692036960935391303255804754787864713189658290361949509917704853428701870609882427423574672772606814823959758208695540116440342488334213300943604780971422918744381486937517952553797134323570131582724393100092308466968491068503301604506186521656059375518680612292667310641047190088814753025794048591445267711939066523165042651430468971452726568222388482323097260496415484997546126185688914792795834046855221759289007609518312601640548469651358391745947588643697900883634533872314566389446271647587564348026861264979727062157272541149018781
c = 16110326928338602237561005337578085623028116490564329920738844771341250444164294693848130674347672763073995755532723894042946521372321947507527854966013459795492930736187058535665041545095683801386814190612817128504426590828954205050425979880047802547011117626354405687170961272200066258220699329112978151044633994329352673342582175349200008181837211288847301836681860817044391028992501763375849046751094019224570802498414368189170656992427042010362385494565216988561215657424755648213390551881450141899860811844684546992754530755092358644968088017107313907435586729574798046187046145596726569637758312033849476689378
n = 16472195897077185060734002588086375750797253422014472876266294484788862733424113898147596402056889527985731623940969291811284437034420929030659419753779530635563455664549165618528767491631867637613948406196511848103083967995689432928779805192695209899686072900265108597626632371718430059561807147486376536203800038054012500244392964187780217667805308512187849789773573138494622201856638931435423778275004491853486855300574479177472267767506041000072575623287557610576406578525902565241580838652860552046216587141709709405062150243990097835181557208274750462554811004137033087430556692966525170882625891516050207318491
c = 11867731823522211833301190385669833752050387304375114576570892885641949969365352586215693183003550684262313893105989683214739695968039039944442567581277252581988489020834299896625977474857889570528169919064941042132119301236852358823696947330423679033138054012027878783478922023431469564210485180679933264749281963405243082505688901662659030897104957499953192201440290084373968716271056483463909282407034181891901928790601973222643210525000717355062752079302291729448234374709852429885984987094307177760741403086538949190424454337896501402430653783597070178968921411867485584517214777073301007918941216316241784521708
n = 13890749889361612188368868998653029697326614782260719535555306236512452110708495623964530174188871342332417484996749651846510646453983388637377706674890018646246874688969342600780781646175634455109757266442675502522791531161284420286435654971819525519296719668701529481662071464145515727217108362496784024871976015116522898184301395037566514980846499856316532479656908169681719288258287756566886281183699239684997698487409138330229321935477734921670373632304542254938831218652340699024011371979519574576890581492623709896310465567043899767342676912434857372520308852745792360420376574037705943820090308501053778144141
c = 6250115196713939477947942995075509357173312813431601073354390451609559579925704891503987992181988654989477525811826607070378476102616752398280691012244301950194800995432882828020405062344160270290542566163969692748126314259624623341922057435728127596172871894887055305291345372720594481096374310285437492746765510292863238933163142677773310305789984897974266961231555124787205980411992251387207335655129551950825339766848166539671565212408741432649813058363660321480995187545006718837863674527475323414266732366507905974800565463011676462244368010182725161416783875646259625352308599198614681446394427674340328493047
n = 21457499145521259498911107987303777576783467581104197687610588208126845121702391694574491025398113729462454256070437978257494064504146718372095872819969887408622112906108590961892923178192792218161103488204912792358327748493857104191029765218471874759376809136402361582721860433355338373725980783308091544879562698835405262108188595630215081260699112737457564998798692048522706388318528370551365364702529068656665853097899157141017378975007689790000067275142731212069030175682911154288533716549782283859340452266837760560153014200605378914071410125895494331253564598702942990036163269043699029806343766286247742865671
c = 6269656777204332618433779865483197625538144405832409880710764183039800286008967127279281167109250083159801218370191973055663058165456565194979210256278526713608759141588082614531352489547674696723140599892318118960648862531538435596775798128845789504910467783731144808685373807716609662688064728614003904579841055786083326311313295311152563668422289435606771091246147867715987583149743032723028324394173498623642539175178996531881058274717907066845565199058931743481410454382746158558886667761300257488769795092777021292335562818583719708133179974425584610403335487082478848975656282384575767178925517257692365828720
'''
import gmpy2
import libnum

e = 65537

n0 = 17524722204224696445172535263975543817720644608816706978363749891469511686943372362091928951563219068859089058278944528021615923888948698587206920445508493551162845371086030869059282352535451058203615402089133135136481314666971507135484450966505425514285114192275051972496161810571035753943880190780759479521486741046704043699838021850105638224212696697865987677760179564370167062037563913329993433080123575434871852732981112883423565015771421868680113407260917902892944119552200927337996135278491046562185003012971570532979090484837684759828977460570826320870379601193678304983534424368152743368343335213808684523217
c0 = 6870605439714128574950893771863182370595667973241984289208050776870220326525943524507319708560433091378319367164606150977103661770065561661544375425887970907060665421562712515902428061727268441585629591525591001533188276465911918724808701356962871139957343861919730086334623932624184172272488406793955068827527130338853980609365042071290967556159598511667974987218999253443575482949258292953639729393456515185185102248985930422080581185292420347510600574229080211050520146551505605537486989306457793451086767402197128573781597156939709237045132856159368959981648969874765462190363842275826077556314448408825308218451

n1 = 24974121071274650888046048586598797033399902532613815354986756278905133499432183463847175542164798764762683121930786715931063152122056911933710481566265603626437742951648885379847799327315791800670175616973945640322985175516271373004547752061826574576722667907302681961850865961386200909397231865804894418194711076667760169256682834206788730947602211228930301853348503098156592000286467190760378847541148772869356389938999094673945092387627113807899212568399028514283219850734634544982646070106811651490010946670117927664594365986238107951837041859682547029079035013475238052160645871718246031144694712586073789250183
c1 = 10324627733161143472233272675096997859064721978612320424254305978486200326061730105384511258706433940176741256952824288120499229240005823611541292676234913505775165761543820764046537413943393325463602612485849366939102550336256797820440347815027443410399157963547486098366749815425187247171697678576246606105486928212486117878157055321965270364583625270716186820068538749425299073309429589410882809098930213978117176627031795312102177342499674234163614021182116065492884880492891668658240362567156235958605768725892407536211503981819707919444725863397622629226309480836486427388484176463279384813974310500625102568341

n2 = 14215826065753265334521416948225868542990756976323308408298887797364519400310818641526401662106853573185085731682502059761982246604277475488691297554851873224516934619888327644352138127883043558424300092247604877819821625587944308487310522092440517150600171819145803937177931473336108429889165189521078678397694303305705260759351843006130968234071638035667854938070597400634242396852782331461576526836227336952718230741560369621645218729592233657856104560425642219241082727756696967324334634822771842625681505869025740662258929200756109704988223034840699133778958569054445520305361142302393767439478256174414187983763
c2 = 415916446053083522663299405080903121619846594209033663622616979372099135281363175464579440520262612010099820951944229484417996994283898028928384268216113118778734726335389504987546718739928112684600918108591759061734340607527889972020273454098314620790710425294297542021830654957828983606433731988998097351888879368160881316237557097381718444193741788664735559392675419489952796677690968481917700683813252460912749931286739585465657312416977086336732056497161860235343155953578618273940135486362350057858779130960380833359506761436212727289297656191243565734621757889931250689354508999144817518599291078968866323093

n3 = 12221355905532691305226996552124162033756814028292708728711809229588190407700199452617060657420166395065565154239801465361510672853972152857415394695376825120759202857555325904640144375262531345320714166285999668052224661520834318497234299585219832943519644095197479639328120838919035625832361810964127485907587199925564724081163804724975965691571850962714258888527902920462746795712011579424322515292865504642938090200503979483095345893697972170153990274670257331483858538617460680462369680572833191232126527727222302641204529110948993583190295067970240051042000918629138767209918572311469915774910003970381965123241
c3 = 2248834602646305164283014556051672824689884721514190813323189875541899566338153534858709617544459297836048770439230174669883719627734394673012731609952869246171300132019334542245094425654362711870373095782083791160029789553806741967408922001051006100049326921742208757147339981269528740944842177729701945606827918253016001436218891580980192743564642120923356793292885805519110411357830040053435569937296612987581482128241218218550319154933831743819546558930918761162723110000328532730751591375727881221199739397698390594797621758011191224528339478784930214820615602510460640307707682865125229937141010351138099874025

n4 = 18152103454920389919231636321286527841833809319334215885641536161086810144890443857211776387914779781628740172079478910188540146498426564211851629962338413488555121865779016981727229209606498886170396500155102635962395243364899026418106378234307821492609778555173516000309435730752571818439328803899462791834490025768785383592935046996428331508608555503567191807692523852530836008436655164751054189301721070209363416058642811329040202582026786024825518381761299547703962502636888833428457116986351812252188468878701301184044948733274488264320930936362549028124581962244201377136969591119942276742760215403738913067567
c4 = 2797812094994121597295362327809389195134238119144547570610194659000554967367804835006774413888965325870488368112707535584687083342412367127561646136089638402907513075405746055834487062923240856950047936297155455745928810738711368950139327254040579266046642851362228893522740216519732851152162928545416236075387903789535000820423985522550638100049857678600662008021574841083416323980817348573062083159710189689337626277009675683473560325178417766400002763719953723259300977655801234386662217462862844994462505601804422871991694828697337752697234180117437785537788728412520613916334045368736691714704501962513954509705

n5 = 22877887459293720334652698748191453972019668578065068224653972884599636421200068659750242304040301306798039254241668648594556654589309801728248683586229288074709849246660525799452637187132633064172425677552176203292787732404537215347782229753837476655088638984496409603054524994383358547132112778403912563916886533181616856401929346567686400616307916690806467019665390260267596320840786982457521423178851498130935577260638269429250197050326097193841333205073650802709022947551398142692735680419453533128176592587955634333425401930362881423044363132586170013458300714163531162544301477356808388416864173949089028317961
c5 = 12271947322974809255127222556723394446467844330408506340843897575503534175121932185624776713618037572593449207329510171212097269297133492090526270770286000839978630002819714376964416081198925899119135271459404333829811516667576167576916805217016117373027245648473458331936273975110163065432285322832123169216976420362833557809289561705091817949915218278430834098156335989014645979633658818904753942786129126233956314517292746008579152368541316795082120147520597254020266752859205131887527661767589367756335766220841483940854397440079467053684289006956034944336788288196391829411432383541473132962783883758561108297747

n6 = 19844333358004073542783728196775487079202832688982038135532362073659058674903791697765527614270399097276261983744620537925712167578187109058145015032736796457938148615396547198728652435169126585595701228287449135664667959433491335769206692390262797325133960778920452511673878233190120432257482339068405290918739453464061987163074129048150451046315248186376609350095502130018696275764450248681787926130463463923862832714969425813770847493135627599129546112143050369344208092649256659330284904392961574494907186727388685504929586018639846040474616307662546605623294842316524163106100888851228858194942825157286544846177
c6 = 9531264751315473345056673937611382755236533664089452852716992791452558274873158812669513178040971923528201631609089069182049526587423864397527252061341857426422965190913745048414029690931254119437249218321954899956104589066479231204536856131403590472063496956452030342299863907499976917750846369802185896519725837163530049157920978007252920334447236842959033879772444475877613295594785710745889554296655932909212643500877218304116451889820444820534937901427158918411546484157737612926382420354101675658160847653151539420222526999426483473829341628599881460824765758346670633385844187252696874025582747177333702736465

n7 = 16956880944655068255446705024149899655327230949463546092744762226005904114738078692036960935391303255804754787864713189658290361949509917704853428701870609882427423574672772606814823959758208695540116440342488334213300943604780971422918744381486937517952553797134323570131582724393100092308466968491068503301604506186521656059375518680612292667310641047190088814753025794048591445267711939066523165042651430468971452726568222388482323097260496415484997546126185688914792795834046855221759289007609518312601640548469651358391745947588643697900883634533872314566389446271647587564348026861264979727062157272541149018781
c7 = 16110326928338602237561005337578085623028116490564329920738844771341250444164294693848130674347672763073995755532723894042946521372321947507527854966013459795492930736187058535665041545095683801386814190612817128504426590828954205050425979880047802547011117626354405687170961272200066258220699329112978151044633994329352673342582175349200008181837211288847301836681860817044391028992501763375849046751094019224570802498414368189170656992427042010362385494565216988561215657424755648213390551881450141899860811844684546992754530755092358644968088017107313907435586729574798046187046145596726569637758312033849476689378

n8 = 16472195897077185060734002588086375750797253422014472876266294484788862733424113898147596402056889527985731623940969291811284437034420929030659419753779530635563455664549165618528767491631867637613948406196511848103083967995689432928779805192695209899686072900265108597626632371718430059561807147486376536203800038054012500244392964187780217667805308512187849789773573138494622201856638931435423778275004491853486855300574479177472267767506041000072575623287557610576406578525902565241580838652860552046216587141709709405062150243990097835181557208274750462554811004137033087430556692966525170882625891516050207318491
c8 = 11867731823522211833301190385669833752050387304375114576570892885641949969365352586215693183003550684262313893105989683214739695968039039944442567581277252581988489020834299896625977474857889570528169919064941042132119301236852358823696947330423679033138054012027878783478922023431469564210485180679933264749281963405243082505688901662659030897104957499953192201440290084373968716271056483463909282407034181891901928790601973222643210525000717355062752079302291729448234374709852429885984987094307177760741403086538949190424454337896501402430653783597070178968921411867485584517214777073301007918941216316241784521708

n9 = 13890749889361612188368868998653029697326614782260719535555306236512452110708495623964530174188871342332417484996749651846510646453983388637377706674890018646246874688969342600780781646175634455109757266442675502522791531161284420286435654971819525519296719668701529481662071464145515727217108362496784024871976015116522898184301395037566514980846499856316532479656908169681719288258287756566886281183699239684997698487409138330229321935477734921670373632304542254938831218652340699024011371979519574576890581492623709896310465567043899767342676912434857372520308852745792360420376574037705943820090308501053778144141
c9 = 6250115196713939477947942995075509357173312813431601073354390451609559579925704891503987992181988654989477525811826607070378476102616752398280691012244301950194800995432882828020405062344160270290542566163969692748126314259624623341922057435728127596172871894887055305291345372720594481096374310285437492746765510292863238933163142677773310305789984897974266961231555124787205980411992251387207335655129551950825339766848166539671565212408741432649813058363660321480995187545006718837863674527475323414266732366507905974800565463011676462244368010182725161416783875646259625352308599198614681446394427674340328493047

n10 = 21457499145521259498911107987303777576783467581104197687610588208126845121702391694574491025398113729462454256070437978257494064504146718372095872819969887408622112906108590961892923178192792218161103488204912792358327748493857104191029765218471874759376809136402361582721860433355338373725980783308091544879562698835405262108188595630215081260699112737457564998798692048522706388318528370551365364702529068656665853097899157141017378975007689790000067275142731212069030175682911154288533716549782283859340452266837760560153014200605378914071410125895494331253564598702942990036163269043699029806343766286247742865671
c10 = 6269656777204332618433779865483197625538144405832409880710764183039800286008967127279281167109250083159801218370191973055663058165456565194979210256278526713608759141588082614531352489547674696723140599892318118960648862531538435596775798128845789504910467783731144808685373807716609662688064728614003904579841055786083326311313295311152563668422289435606771091246147867715987583149743032723028324394173498623642539175178996531881058274717907066845565199058931743481410454382746158558886667761300257488769795092777021292335562818583719708133179974425584610403335487082478848975656282384575767178925517257692365828720


n = [n0, n1, n2, n3, n4, n5, n6, n7, n8, n9, n10]
c = [c0, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10]

for i in range(len(n)):
    for j in range(len(n)):
        if (i != j):
            if (gmpy2.gcd(n[i], n[j]) != 1):  # 对不同的n进行 欧几里得算法，以求出最大公约数(p)
                print(i, j)  # 输出对应的n的序号
                p = gmpy2.gcd(n[i], n[j])
                print("p = ", p)
                q = n[i] // p
                print("q = ", q)
                d = gmpy2.invert(e, (p - 1) * (q - 1))
                print("d = ", d)
                m = pow(c[i], d, n[i])
                print("m = ", m)
print(libnum.n2s(int(m)))

4.低指数加密广播攻击（e很小;多组n,c）应用CRT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gmpy2
import libnum
from Crypto.Util.number import long_to_bytes
from sympy.ntheory.modular import crt
 
N1 = int('331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004',5)
c1 = int('310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243',5)
 
N2 = int('302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114',5)
c2 = int('112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344',5)
 
N3 = int('332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323',5)
c3 = int('10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242',5)
 
e = 3
n = [N1,N2,N3]
c = [c1,c2,c3]
resultant, mod = crt(n, c)
value, is_perfect = gmpy2.iroot(resultant, e)
print(long_to_bytes(value))

5.共模攻击(多组c和e;n相同)

当题目给我们很多组c和e，但它们加密使用的模数n相同时，我们可以考虑共模攻击，当e1，e2互质，有gcd(e1,e2)=1，根据扩展欧几里得算法，一定存在整数x,y使得e1x+e2y=1。我们可以调用gmpy2.gcdext()来使用扩展欧几里得算法，以此求出x和y。m = (c1^x*c2^y)modn

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2
from Crypto.Util.number import getPrime,long_to_bytes
 
e1 = 2767
e2 = 3659
n = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111
 
c1 = 20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
c2 = 11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227
 
_,s1, s2 = gmpy2.gcdext(e1, e2)
m = pow(c1, s1, n) * pow(c2, s2, n) % n
print(long_to_bytes(m))

6.dp泄露(提供dp,e,n,c)

dp=d%(p-1)通过爆破k的方式来求出p

1
2
3
4
5
6
7
d = dp + k1 * (p-1) 
d * e = 1 + k2(p-1)(q-1) 
把第二个式子的d代换掉：
e * (dp + k1(p-1)) = 1 + k2(p-1)(q-1)
两边同时对(p-1)取模，消去k
e * dp % (p - 1) = 1
e * dp = 1 + k(p - 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import gmpy2
from Crypto.Util.number import long_to_bytes
 
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
 
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
 
for i in range(1, e):
    if (dp * e - 1) % i == 0:
        if n % (((dp * e - 1) // i) + 1) == 0:
            p = ((dp * e - 1) // i) + 1
            q = n // (((dp * e - 1) // i) + 1)
            d = gmpy2.invert(e, (p-1)*(q-1))
            m = pow(c, d, n)
 
print(m)
print(long_to_bytes(m))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#脚本2
# 已知n、e、dp、c，求m
def decrypt(e,n,c,dp):
    for x in range(1, e):
        if(e*dp%x==1):
            p=(e*dp-1)//x+1
            if(n%p!=0):
                continue
            q=n//p
            phin=(p-1)*(q-1)
            d=gmpy2.invert(e, phin)
            m=gmpy2.powmod(c, d, n)
            if(len(hex(m)[2:])%2==1):
                continue
            print(bytes.fromhex(hex(m)[2:]))

7.dp,dq泄露(给出p,q,dp,dq,c，但是没给e)

1
2
3
4
m1 = c^dpmodp
m2 = c^dqmodq
m = (((m1-m2)*I)%p)*q+m2
其中I为对pq求逆元
1
2
3
4
5
6
7
8
9
10
11
12
import gmpy2
from Crypto.Util.number import long_to_bytes
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
I = gmpy2.invert(q,p)
m1 = pow(c,dp,p)
m2 = pow(c,dq,q)
m = (((m1-m2)*I)%p)*q+m2
print(long_to_bytes(m))
1
2
3
4
5
6
7
8
9
10
11
12
#脚本2
#已知p、q、dp、dq、c，求m。

def decrypt(p,q,dp,dq,c):
    n = p*q
    phin = (p-1)*(q-1)
    dd = gmpy2.gcd(p-1, q-1)
    d=(dp-dq)//dd * gmpy2.invert((q-1)//dd, (p-1)//dd) * (q-1) +dq
    print(d)

    m = gmpy2.powmod(c, d, n)
    print(bytes.fromhex(hex(m)[2:]))

8.e和phi不互素(bad_e)

8.1 e与(p-1)或(q-1)均不互素

需要用到有限域的开方来做，解法：
①分别利用sagemath求解一个模质数p和q意义下的方程x^{e}=c的解；

1
2
3
4
5
6
7
8
e = 
p = 
c = 
R = Zmod(p)['x']; (x,) = R._first_ngens(1) #模p的意义下定义了一个多项式环R
f = x ** e - c
f = f.monic()
res1 = f.roots()
print(res1)
1
2
3
4
5
6
7
8
e = 
q = 
c = 
R = Zmod(q)['x']; (x,) = R._first_ngens(1) #模q的意义下定义了一个多项式环R
f = x ** e - c
f = f.monic()
res2 = f.roots()
print(res2)

②然后利用中国剩余定理遍历得到的根的列表。

1
2
3
4
5
6
7
8
res1 = 
res2 = 
for i in res1:
    for j in res2:
        m = libnum.solve_crt([int(i[0]),int(j[0])],[p,q])
        flag = long_to_bytes(m)
        if b'flag' in flag:
            print(flag)

8.2 e与（p-1）或者(q-1)其中一个不互素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import * # 一个非常好用的crypto库
from gmpy2 import *

n =
p = 
q = 
c = 
e = 
print(gcd(e,p-1))

phi = p-1
#phi = q-1
d = gmpy2.invert(e,phi)
m = pow(c,d,p)
#m=pow(c,d,q)
print(long_to_bytes(m))

9.Robin’s_rsa(特点e=2)

介绍：
https://blog.csdn.net/jcbx_/article/details/101066670

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
n = 
c = 
e = 2
 
# 在线 分解 n 
p = 
q = 
inv_p = gmpy2.invert(p, q)
inv_q = gmpy2.invert(q, p)
mp = pow(c, (p + 1) // 4, p)
mq = pow(c, (q + 1) // 4, q)
a = (inv_p * p * mq + inv_q * q * mp) % n
b = n - int(a)
c = (inv_p * p * mq - inv_q * q * mp) % n
d = n - int(c)
# rabin 加密有四种结果
aa = [a, b, c, d]
 
for i in aa:
    if b'flag' in libnum.n2s(int(i)):
        print(libnum.n2s(int(i)))

10.e特别大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import getPrime

with open("flag.txt","rb") as fs:
    flag = fs.read().strip()

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 0x609778981bfbb26bb93398cb6d96984616a6ab08ade090c1c0d4fedb00f44f0552a1555efec5cc66e7960b61e94e80e7483b9f906a6c8155a91cdc3e4917fa5347c58a2bc85bb160fcf7fe98e3645cfea8458ea209e565e4eb72ee7cbb232331a862d8a84d91a0ff6d74aa3c779b2b129c3d8148b090c4193234764f2e5d9b2170a9b4859501d07c0601cdd18616a0ab2cf713a7c785fd06f27d68dff24446d884644e08f31bd37ecf48750e4324f959a8d37c5bef25e1580851646d57b3d4f525bc04c7ddafdf146539a84703df2161a0da7a368675f473065d2cb661907d990ba4a8451b15e054bfc4dd73e134f3bf7d8fa4716125d8e21f946d16b7b0fc43
m = int.from_bytes(flag,"big")
c = pow(m,e,n)

print(n) # n=0xbaa70ba4c29eb1e6bb3458827540fce84d40e1c966db73c0a39e4f9f40e975c42e02971dab385be27bd2b0687e2476894845cc46e55d9747a5be5ca9d925931ca82b0489e39724ea814800eb3c0ea40d89ebe7fe377f8d3f431a68d209e7a149851c06a4e67db7c99fcfd9ec19496f29d59bb186feb44a36fe344f11d047b9435a1c47fa2f8ed72f59403ebb0e439738fd550a7684247ab7da64311690f461e6dce03bf2fcd55345948a3b537087f07cd680d7461d326690bf21e39dff30268cb33f86eeceff412cd63a38f7110805d337dcad25e6f7e3728b53ca722b695b0d9db37361b5b63213af50dd69ee8b3cf2085f845d7932c08b27bf638e98497239
print(c) # 0x45a9ce4297c8afee693d3cce2525d3399c5251061ddd2462513a57f0fd69bdc74b71b519d3a2c23209d74fcfbcb6b196b5943838c2441cb34496c96e0f9fc9f0f80a2f6d5b49f220cb3e78e36a4a66595aa2dbe3ff6e814d84f07cb5442e2d5d08d08aa9ccde0294b39bfde79a6c6dcd2329e9820744c4deb34a039da7933ddf00b0a0469afb89cba87490a39783a9b2f8f0274f646ca242e78a326dda886c213bc8d03ac1a9150de4ba08c5936c3fe924c8646652ef85aa7ac0103485f472413427a0e9d9a4d416b99e24861ca8499500c693d7a07360158ffffa543480758cafff2a09a9f6628f92767764fa026d48a9dd899838505ae16e38910697f9de14

解法：使用RSAwienierHacker.py直接求d

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
'''
Created on Dec 14, 2011

@author: pablocelayes
'''

import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator

def hack_RSA(e,n):
    '''
    Finds d knowing (e,n)
    applying the Wiener continued fraction attack
    '''
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)
    
    for (k,d) in convergents:
        
        #check if d is actually the key
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if(discr>=0):
                t = Arithmetic.is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    print("Hacked!")
                    return d

# TEST functions

def test_hack_RSA():
   # print("Testing Wiener Attack")
   # times = 5
    
   # while(times>0):
       # e,n,d = RSAvulnerableKeyGenerator.generateKeys(1024)
       # print("(e,n) is (", e, ", ", n, ")")
       # print("d = ", d)
        n=
        e = 

        hacked_d = hack_RSA(e, n)
        '''
        if d == hacked_d:
            print("Hack WORKED!")
        else:
            print("Hack FAILED")
        '''
        print("hacked_d = ", hacked_d)
        print("-------------------------")
        #times -= 1
        
if __name__ == "__main__":
    #test_is_perfect_square()
    #print("-------------------------")
    test_hack_RSA()

11.

四.普通例题

1.连分数修复num1/num2

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
from Crypto.Util.number import *
from random import *
from sage.all import *

flag = b'--hidden_message--'
data1 = getPrime(256)
data2 = getPrime(256)
m = bytes_to_long(flag)+data2
prec = 600
ring = RealField(prec)
data3 = ring(data1) / ring(data2)
print(data3)

while True:
    p = randint(2**255, data1)
    q = randint(2**255, data2)
    if isPrime(p) and isPrime(q) and p!=q:
        break

n = p*q
e = 65537
leak = pow(p-q, data1, data1*data2)
c = pow(m, e, n)
print(c)
print(n)
print(leak)
'''
1.42870767357206600351348423521722279489230609801270854618388981989800006431663026299563973511233193052826781891445323183272867949279044062899046090636843802841647378505716932999588
1046004343125860480395943301139616023280829254329678654725863063418699889673392326217271296276757045957276728032702540618505554297509654550216963442542837
2793178738709511429126579729911044441751735205348276931463015018726535495726108249975831474632698367036712812378242422538856745788208640706670735195762517
1788304673303043190942544050868817075702755835824147546758319150900404422381464556691646064734057970741082481134856415792519944511689269134494804602878628
'''

①连分数修复num1/num2

求解data1和data2想到的是应用连分数攻击，找到分子分母256bit的渐进分数逼近data3

1
2
3
4
5
6
7
8
9
#sage
data3=

c = continued_fraction(data3)
alist = c.convergents()
for i in alist:
    a = str(i).split('/')
    if len(a)>1 and gcd(int(a[0]),int(a[1])) == 1 and is_prime(int(a[0])) and is_prime(int(a[1])) and int(a[0]).bit_length()==256 and int(a[1]).bit_length()==256:
            print(a

②解密leak得到p-q

image

1
2
3
4
5
6
7
8
9
data1=
data2=
leak=
e=data1
n=data1*data2
phi = (data1-1) * (data2-1)
d = gmpy2.invert(e,phi)
p_q = gmpy2.powmod(leak,d,n)
print(p_q)

③求解p、q

1
2
3
4
5
6
7
8
9
10
#求解p，q
p_q=
c=
n=
e = 65537
var("p,q")
eq1= p-q ==p_q
eq2= p*q ==n
sol = solve([eq1,eq2], p, q)
print(sol)

④结果

1
2
3
4
5
6
7
8
9
10
data2=

e = 65537
p = 
q = 
phi = (q-1) * (p-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)-data2
print(m)
print(long_to_bytes(m))

2.

五.交互例题

1.crt-rsa

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
题目：
'''from Crypto.Util.number import bytes_to_long, getPrime
import socketserver
import json

FLAG = b'HTB{--REDACTED--}'


class TimeCapsule():

    def __init__(self, msg):
        self.msg = msg
        self.bit_size = 1024
        self.e = 5

    def _get_new_pubkey(self):
        while True:
            p = getPrime(self.bit_size // 2)
            q = getPrime(self.bit_size // 2)
            n = p * q
            phi = (p - 1) * (q - 1)
            try:
                pow(self.e, -1, phi)
                break
            except ValueError:
                pass

        return n, self.e

    def get_new_time_capsule(self):
        n, e = self._get_new_pubkey()
        m = bytes_to_long(self.msg)
        m = pow(m, e, n)

        return {"time_capsule": f"{m:X}", "pubkey": [f"{n:X}", f"{e:X}"]}


def challenge(req):
    time_capsule = TimeCapsule(FLAG)
    while True:
        try:
            req.sendall(
                b'Welcome to Qubit Enterprises. Would you like your own time capsule? (Y/n) '
            )
            msg = req.recv(4096).decode().strip().upper()
            if msg == 'Y' or msg == 'YES':
                capsule = time_capsule.get_new_time_capsule()
                req.sendall(json.dumps(capsule).encode() + b'\n')
            elif msg == 'N' or msg == "NO":
                req.sendall(b'Thank you, take care\n')
                break
            else:
                req.sendall(b'I\'m sorry I don\'t understand\n')
        except:
            # Socket closed, bail
            return


class MyTCPRequestHandler(socketserver.BaseRequestHandler):

    def handle(self):
        req = self.request
        challenge(req)


class ThreadingTCPServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass


def main():
    socketserver.TCPServer.allow_reuse_address = True
    server = ThreadingTCPServer(("0.0.0.0", 1337), MyTCPRequestHandler)
    server.serve_forever()


if __name__ == '__main__':
    main()
'''
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
from sympy.ntheory.modular import crt
from sympy import integer_nthroot
from Crypto.Util.number import long_to_bytes
#nc 环境 port     三次Y得到time_capsule和pubkey
##加密输出 1
c1 = 0x2D5BFF95F5E4C1A29C6912251389A828DD45A89DC915E1FB6F19D1BC70CE2CF49A8A600C956017DDB55471141C1283E832DE7F87D74A6FFCD8089228A8E25A97BF49B86B48D77BCA2629EF8AA8988E7B13352254596248C2B05ED033A914182DBD42153867EC7190B18035D34A0098EC3BEBE2933055B9337D05B32106210AAF

n1 = 0x636E550EDFA733E5D8531CE0B8283DF85447C606EFE44609E9E62F639219AD7B3D0D489D0F47325D64DE031BFB5C90C0EFB0FBEC8F1D04B3B336E0ABBBDA6634B2BAB24DCD74E3561FA635FA72E599F1EE522FF124DABB53035DEC0F6F1C9439AFDAF30144BE79386D11D90AFCDCFA9552E0DF6037F48B55BDBB30B2FC776ED9

##加密输出 2
c2= 0x6A3D5E0B56CAC5719C4D7ED0C1FBE0C2683B8CED7BB996EE9844DFA096C05B66BF18F136C45540EE263F8431F7D258A4B9EE3D419429845083673E363D343CFD9E329B226C787388B20D2037AB8F2D2D29EA5A76EA650C687385F844DE43E68EF733F07A8431C74BB48036CA7B1197E04FC5EF161CAAB891804A8EBCB0D2CE53

n2= 0x939C324269BDF0A0A8EB294EB0808BBFD2151913FDD1C100A5AA33D442EC1FB487B37CF87CF1B9FBB538EB51223DC193FF074F825B018EE548496CCE7762849408AD300582D8B9F7BF684377766AF7884C04BA23F217624D979AA84155661BCE0CB3383DCD2F1EB3D8324195B45F8837CF29A7E61FBA9AA52B369CB74C0D9639

##加密输出 3
c3 = 0x385D2213C7D7314F333727937FCB692B13AF214D88E0F6C473977810A99744CE34A5FA0FEEEA367572B4F23CC40481AF535D2537B2E28894F39CB1AF8D617152782EE3268B469E3F92E7666F17FABF5DCC275589AE0C08FF2A081442AF1AFE4A094C8B60748B6B91DF1C947BF53AB87806A33D8AE7CDE0BECBC250808DEFCBD

n3 = 0x9638FC9CA2DB7835EFE47F2C93EB261A7A028909BA866DA8C449DE4191FCAF3EAB68E879882B31817F289C8EA22135B32650812C24959A603288992C37F52C8D02C721DB7559D839B48118AA385304A616A29CEB48E02E968CC49719C3549CA72296605CD329E67270430025D65C5B854B8ECF48BFBCFA12904D63B7883BD84B

##使用中国余数定理计算m的e次方
x = crt([n1, n2, n3], [c1, c2, c3], check=True)
print("x=", x)

##开e次方求解m
m = integer_nthroot(x[0], 5)
print("m=", m)

##输出明文
flag = long_to_bytes(m[0])
print("flag=", flag)
文章作者: harmor
文章链接: https://harmor123.github.io/harmor.github.io/harmor.github.io/2023/11/01/test/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 harmor !
CTF crypto
赏
评论