跳转至
2021 | 中国科学技术大学第八届信息安全大赛 | Math

HackerGame - Easy RSA

题目

自从 Hackergame 2018 公然揭露了大整数可以被神童口算分解的事实，RSA 在 hackergame 中已经只能处于低分值的地位了。如果不在其名称前面加上 Easy 这个单词，似乎就会显得完全对不起其他题目。

更何况，在本题的附件中，你还获得了构造 p 和 q 的方式。数理基础扎实的你应该可以轻松解决这些问题吧。

Easy_RSA.py 
 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 math
import sympy
from Crypto.Util.number import *

e = 65537


def get_p():
    x = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391760451
    y = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391661439
    value_p = sympy.nextprime((math.factorial(y)) % x)  # Hint：这里直接计算会溢出，请你仔细观察 x 和 y 的特征
    return value_p


def get_q():
    value = [getPrime(256)]
    for i in range(1, 10):
        value.append(sympy.nextprime(value[i - 1]))
    print("value[-1] = ", value[-1])
    # value[-1] = 80096058210213458444437404275177554701604739094679033012396452382975889905967
    n = 1
    for i in range(10):
        n = n * value[i]
    q = getPrime(512)
    value_q = pow(q, e, n)
    print("value_q = ", value_q)
    # value_q = 5591130088089053683141520294620171646179623062803708281023766040254675625012293743465254007970358536660934858789388093688621793201658889399155357407224541324547522479617669812322262372851929223461622559971534394847970366311206823328200747893961649255426063204482192349202005330622561575868946656570678176047822163692259375233925446556338917358118222905050574458037965803154233167594946713038301249145097770337253930655681648299249481985768272321820718607757023350742647019762122572886601905212830744868048802864679734428398229280780215896045509020793530842541217790352661324630048261329493088812057300480085895399922301827190211956061083460036781018660201163819104150988531352228650991733072010425499238731811243310625701946882701082178190402011133439065106720309788819
    return sympy.nextprime(q)

# this destroyes the rsa cryptosystem
p = get_p()
q = get_q()

m = int.from_bytes(open("flag.txt", "rb").read(), "big")
c = pow(m, e, p * q)
print("c = ", c)
# c = 110644875422336073350488613774418819991169603750711465190260581119043921549811353108399064284589038384540018965816137286856268590507418636799746759551009749004176545414118128330198437101472882906564195341277423007542422286760940374859966152871273887950174522820162832774361714668826122465471705166574184367478

解题思路

  • 加密方式和 RSA 没有区别，只需要得到加密使用的 p 和 q 就可以了！

  • p 值为 y 的阶乘模 x 的下一个质数，由于 y 值较大，直接求阶乘比较困难。仔细观察 y 与 x 差值较小，且 x 为质数，\(y < x，y > x/2\)，可以使用威尔逊定理快速求解

    \((x-1)! \equiv -1 \,(mod \, x)\)

    \((y-1)! \equiv -1 \,(mod \, y)\)

    \(y! * (y+1) * ... * (x-2) * (x-1) \equiv -1 \,(mod \, x)\)

    \(y! \equiv -[(y+1) * ... * (x-2) * (x-1)]^{-1} \, (mod \, x)\)

  • 重写 get_p() 函数，求逆元板子指路 -> easy_RSA 

    1
2
3
4
5
6
7
8
9
    def get_p():
    x = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391760451
    y = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391661439
    multi = 1
    for i in range(y + 1, x):
        multi = (i * multi) % x
    factor = (x - modinv(multi, x)) % x
    value_p = sympy.nextprime(factor)
    return value_p

  • q 值求解类似于 RSA 解密，先使用 prevprime 倒推 value 获得 \(n\) 的所有因数，从而获得 \(\varphi(n)\)，进而求出 \(d\)

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    def get_real_q():
    value = [80096058210213458444437404275177554701604739094679033012396452382975889905967]
    for i in range(1, 10):
        value.append(sympy.prevprime(value[i - 1]))
    value.reverse()
    n = fn = 1
    for i in range(10):
        fn *= (value[i] - 1)
        n *= value[i]
    d = modinv(e, fn)
    value_q = 5591130088089053683141520294620171646179623062803708281023766040254675625012293743465254007970358536660934858789388093688621793201658889399155357407224541324547522479617669812322262372851929223461622559971534394847970366311206823328200747893961649255426063204482192349202005330622561575868946656570678176047822163692259375233925446556338917358118222905050574458037965803154233167594946713038301249145097770337253930655681648299249481985768272321820718607757023350742647019762122572886601905212830744868048802864679734428398229280780215896045509020793530842541217790352661324630048261329493088812057300480085895399922301827190211956061083460036781018660201163819104150988531352228650991733072010425499238731811243310625701946882701082178190402011133439065106720309788819
    return sympy.nextprime(pow(value_q, d, n))

  • p、q 和 e 都得到了，解密就是分分钟的事啦 XD

    1
2
3
4
5
    fn = (p - 1) * (q - 1)
d = modinv(e, fn)
print(long_to_bytes(pow(c, d, p * q)))

# b'flag{CRYPT0_1s_Interesting!}'

参考资料

最后更新: 2021年11月1日 11:44:30
Contributors: YanhuiJessica

评论