做题

发表于 分类于 阅读次数： Waline： 本文字数： 273 阅读时长 ≈ 1 分钟

做题记录

Defective RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import getPrime, inverse, bytes_to_long

e = 1440

p = getPrime(1024)
q = getPrime(1024)
n = p * q

flag
c = pow(bytes_to_long(flag), e, n)

print(f"e = {e}")
print(f"p = {p}")
print(f"q = {q}")
print(f"c = {c}")

# e = 1440
# p = 108625855303776649594296217762606721187040584561417095690198042179830062402629658962879350820293908057921799564638749647771368411506723288839177992685299661714871016652680397728777113391224594324895682408827010145323030026082761062500181476560183634668138131801648343275565223565977246710777427583719180083291
# q = 124798714298572197477112002336936373035171283115049515725599555617056486296944840825233421484520319540831045007911288562132502591989600480131168074514155585416785836380683166987568696042676261271645077182221098718286132972014887153999243085898461063988679608552066508889401992413931814407841256822078696283307
# c = 4293606144359418817736495518573956045055950439046955515371898146152322502185230451389572608386931924257325505819171116011649046442643872945953560994241654388422410626170474919026755694736722826526735721078136605822710062385234124626978157043892554030381907741335072033672799019807449664770833149118405216955508166023135740085638364296590030244412603570120626455502803633568769117033633691251863952272305904666711949672819104143350385792786745943339525077987002410804383449669449479498326161988207955152893663022347871373738691699497135077946326510254675142300512375907387958624047470418647049735737979399600182827754

gcd(e,phi)=20，直接构造多项式环\[f = x^20-c\;mod\;p(q)\]，之后对结构用crt即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
e = 1440
p = 108625855303776649594296217762606721187040584561417095690198042179830062402629658962879350820293908057921799564638749647771368411506723288839177992685299661714871016652680397728777113391224594324895682408827010145323030026082761062500181476560183634668138131801648343275565223565977246710777427583719180083291
q = 124798714298572197477112002336936373035171283115049515725599555617056486296944840825233421484520319540831045007911288562132502591989600480131168074514155585416785836380683166987568696042676261271645077182221098718286132972014887153999243085898461063988679608552066508889401992413931814407841256822078696283307
c = 4293606144359418817736495518573956045055950439046955515371898146152322502185230451389572608386931924257325505819171116011649046442643872945953560994241654388422410626170474919026755694736722826526735721078136605822710062385234124626978157043892554030381907741335072033672799019807449664770833149118405216955508166023135740085638364296590030244412603570120626455502803633568769117033633691251863952272305904666711949672819104143350385792786745943339525077987002410804383449669449479498326161988207955152893663022347871373738691699497135077946326510254675142300512375907387958624047470418647049735737979399600182827754

 
R.<x> = Zmod(p)[]
f = x ^ e - c
f = f.monic()
res1 = f.roots()
 
R.<x> = Zmod(q)[]
f = x ^e - c
f = f.monic()
res2 = f.roots()

for i in res1:
    for j in res2:
        m=crt(int(i[0]),int(j[0]),p,q)
        print(long_to_bytes(m))

也可以这么构造： \[ (m * x) ^ e \;= \;c\;(mod \;n)\\ x ^ e \;= \;1 \;(mod \;n) \] 然后寻求这个新多项式下的解x即可

1
2
3
4
5
6
7
8
9
10
def roots_of_unity(e, phi, n, rounds=500):
   
    phi_coprime = phi
    while cun.GCD(phi_coprime, e) != 1:
        phi_coprime //= cun.GCD(phi_coprime, e)

    roots = set(pow(i, phi_coprime, n) for i in range(1, rounds))

    assert all(pow(root, e, n) == 1 for root in roots)
    return roots, phi_coprime

pollards_RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from gmpy2 import is_prime, mpz
from random import SystemRandom

rand = SystemRandom()
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]


def get_prime(bit_length):
    while True:
        x = mpz(1)
        while x.bit_length() < bit_length:
            x *= rand.choice(PRIMES)
        if is_prime(x + 1):
            return x + 1

p = get_prime(1024)
q = get_prime(1024)
n = p * q
print(f"n = {n}")

用pollards_rho方法分解n。这也说明了用小素数来生成素数非常不安全

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2
import math
from functools import reduce
from operator import mul

PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]
def pollards_rho(n):
    x = 2
    for _ in range(30):
        x = pow(pow(x, reduce(mul, PRIMES), n),reduce(mul, PRIMES),n)
        g = gmpy2.gcd(x - 1, n)
        if 1 < g < n:
            print(_)
            return g

x求值那里可以从两轮改成一轮，两轮的目的是加快速度，但有时候可能会错失解，对这题来说问题不大

Key exchange

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
import random
import hashlib

# Mac/Linux: pip3 install pycryptodome
# Windows: py -m pip install pycryptodome
import Crypto.Util.number as cun
from Crypto.Cipher import AES

rand = random.SystemRandom()

def diffie_hellman(message: bytes):
    p = cun.getPrime(512)
    g = 5
    print(f"p = {p}")
    print(f"g = {g}")

    a = rand.randrange(2, p - 1)  # private key
    A = pow(g, a, p)  # public key

    # g ^ a === A  (mod p)
    # It's computationally infeasible for anyone else to derive a from A
    print(f"A = {A}")

    B = int(input("Give me your public key B: "))
    if not (1 < B < p - 1):
        print("Suspicious public key")
        return

    # B ^ a === (g ^ b) ^ a === g ^ (ab)  (mod p)
    # Nobody can derive this shared secret except us!
    shared_secret = pow(B, a, p)

    # Use AES, a symmetric cipher, to encrypt the flag using the shared key
    key = hashlib.sha1(cun.long_to_bytes(shared_secret)).digest()[:16]
    cipher = AES.new(key, AES.MODE_ECB)
    ciphertext = cipher.encrypt(message)
    print(f"ciphertext = {ciphertext.hex()}")


print("I'm going to send you the flag.")
print("However, I noticed that an FBI agent has been eavesdropping on my messages,")
print("so I'm going to send it to you in a way that ONLY YOU can decrypt the flag.")
print()
diffie_hellman(FLAG)

就是个最基本的DH密钥交换，知道概念即可