CryptoHack 刷题记录

RSA

STARTER

RSA START1

计算 $101^{17} mod\ 22663$

RSA START2

pow(12, 0x10001, 17*23)

RSA START3

计算欧拉函数

p = 857504083339712752489993810777
q = 1029224947942998075080348647219

phi = (p - 1) * (q - 1)

RSA START4

inverse(e, (p - 1)*(q - 1))

RSA START5

www.factordb.com 分解N

PRIMES PART 1

Factoring

yafu或者factordb网站 分解

Inferius Prime

在线网站分解得到

p = 752708788837165590355094155871
q = 986369682585281993933185289261

Monoprime

N是素数，那么 $phi=N-1$

$d = inverse(e, N-1)$

Square Eyes

根据题目意思，生成了一个素数p，并且 $N=p^2$

则

$$phi=p^2-p$$

Manyprime

用工具yafu可以分解得到32个因子

PUBLIC EXPONENT

SALTY

e=1, m=c

Modulus Inutilis

低加密指数

from Crypto.Util.number import *
import gmpy2

n = ''''''
e = 3
ct = ''''''

if gmpy2.iroot(ct, e)[1]:
    m = gmpy2.iroot(ct, e)[0]
else:
    print('error')
print(long_to_bytes(m))

Everything is Big

维纳攻击

Crossed Wires

$$c\equiv m^{e_0e_1e_2e_3e_4} \pmod n \\ ed\equiv1\pmod {\phi(n)}=>k_1\phi(n)=ed-1 \\ 令x=e_0e_1e_2e_3e_4，xd_2\equiv1\pmod{k_1\phi(n)}，也就是xd_2=k_1k_2\phi(n)+1 \\ 两边同余\phi(n)，得xd_2\equiv1\pmod{\phi(n)}$$

from Crypto.Util.number import *
import gmpy2

e0 = 103231
e1 = 97117
e2 = 69557
e3 = 108533
e4 = 106979

n = ''''''
e = 0x10001
d = ''''''
c = ''''''

d2 = inverse(e0*e1*e2*e3*e4, e*d - 1)
m = pow(c, d2, n)
print(long_to_bytes(m))

Everything is Still Big

不满足维纳攻击，但是可以用Boneh Durfee方法，github上有脚本

Endless Emails

根据题目提示有些密文是由相同的明文加密来的，广播攻击，e=3，所以遍历组合$C_{7}^{3}$，用中国剩余定理求解

sage:

from Crypto.Util.number import *
from itertools import *
from gmpy2 import *

'''
outputs
'''

n = [n0, n1, n2, n3, n4, n5, n6]
c = [c0, c1, c2, c3, c4, c5, c6]

for i, j, k in list(combinations(range(7), 3)):
    cbar = CRT_list([c[i], c[j], c[k]], [n[i], n[j], n[k]])
    if iroot(cbar, 3)[1]:
        m = iroot(cbar, 3)[0]
        flag = long_to_bytes(m)
        if b'crypto' in flag:
            print(flag)
            break
    else:
        print('no root found')

PRIMES PART 2

Infinite Descent

从生成素数的过程看，p和q相差不大，可以用费马分解或者用yafu工具分解

Marin’s Secrets

p和q的形式是$2^k-1$，题目给的n是4484位的，k最大就是4483，那么就可以进行爆破找因子

from Crypto.Util.number import *
from gmpy2 import is_prime

n = '''''' 
e = 65537
c = ''''''

for i in range(4484):
    if is_prime(2**i - 1) == False:
        continue
    if n % 2**i - 1 == 0:
        p = 2**i - 1
        q = n // p
        phi = (p - 1) * (q - 1)
        d = inverse(e, phi)
        m = pow(c, d, n)
        if b'crypto' in long_to_bytes(m):
            print(long_to_bytes(m))
            break