GoogleCTF2022 复现(更新中)

把鼠鼠给难到了

CYCLING

task

"""
It is well known that any RSA encryption can be undone by just encrypting the
ciphertext over and over again. If the RSA modulus has been chosen badly then
the number of encryptions necessary to undo an encryption is small.
If n = 0x112b00148621 then only 209 encryptions are necessary as the following
example demonstrates:

>>> e = 65537
>>> n = 0x112b00148621
>>> pt = 0xdeadbeef
>>> # Encryption
>>> ct = pow(pt, e, n)
>>> # Decryption via cycling:
>>> pt = ct
>>> for _ in range(209):
>>>   pt = pow(pt, e, n)
>>> # Assert decryption worked:
>>> assert ct == pow(pt, e, n)

However, if the modulus is well chosen then a cycle attack can take much longer.
This property can be used for a timed release of a message. We have confirmed
that it takes a whopping 2^1025-3 encryptions to decrypt the flag. Pack out
your quantum computer and perform 2^1025-3 encryptions to solve this
challenge. Good luck doing this in 48h.
"""

e = 65537
n = 0x99efa9177387907eb3f74dc09a4d7a93abf6ceb7ee102c689ecd0998975cede29f3ca951feb5adfb9282879cc666e22dcafc07d7f89d762b9ad5532042c79060cdb022703d790421a7f6a76a50cceb635ad1b5d78510adf8c6ff9645a1b179e965358e10fe3dd5f82744773360270b6fa62d972d196a810e152f1285e0b8b26f5d54991d0539a13e655d752bd71963f822affc7a03e946cea2c4ef65bf94706f20b79d672e64e8faac45172c4130bfeca9bef71ed8c0c9e2aa0a1d6d47239960f90ef25b337255bac9c452cb019a44115b0437726a9adef10a028f1e1263c97c14a1d7cd58a8994832e764ffbfcc05ec8ed3269bb0569278eea0550548b552b1
ct = 0x339be515121dab503106cd190897382149e032a76a1ca0eec74f2c8c74560b00dffc0ad65ee4df4f47b2c9810d93e8579517692268c821c6724946438a9744a2a95510d529f0e0195a2660abd057d3f6a59df3a1c9a116f76d53900e2a715dfe5525228e832c02fd07b8dac0d488cca269e0dbb74047cf7a5e64a06a443f7d580ee28c5d41d5ede3604825eba31985e96575df2bcc2fefd0c77f2033c04008be9746a0935338434c16d5a68d1338eabdcf0170ac19a27ec832bf0a353934570abd48b1fe31bc9a4bb99428d1fbab726b284aec27522efb9527ddce1106ba6a480c65f9332c5b2a3c727a2cca6d6951b09c7c28ed0474fdc6a945076524877680
# Decryption via cycling:
pt = ct
for _ in range(2**1025 - 3):
  pt = pow(pt, e, n)
# Assert decryption worked:
assert ct == pow(pt, e, n)

# Print flag:
print(pt.to_bytes((pt.bit_length() + 7)//8, 'big').decode())

task的代码简单到令人发指，给出一个明文，在加密次后又恢复到明文。往往代码简单的题都很难，这道题完美符合这一点

在做题前先引入一个数学知识——Carmichael数与Carmichael函数

Carmichael数

定义：使得成立的最小正整数，其中，将记作

（是不是感觉和费马小定理有点像？其实费马小定理也是Carmichael函数的特殊情况）

Carmichael函数

其中第三条是根据唯一因式分解定理得出：任何的整数都可以用唯一的方式写成

当的因式全为素数时，

现在来分析task：

因为，可推得，再推得

用task给出的small case可以验证一下这个推断的正确性

此题给出的k为，这种大数真的拿去加密的话不知道什么时候才能跑完。所以要从Carmichael函数上入手

根据上面的推断，，而，因此我们对进行质因数分解，可以得到非常有用的东西。

在本题中，，，故。因此我们将的所有因式进行组合并相乘

1
2
3

factor(6) = 1 * 2 * 3
list = [(1,),(2,),(3,),(1,2),(1,3),(2,3),(1,2,3)]
res = 1 * 2 * 3 * (1 * 2) * (1 * 3) * (2 * 3) * (1 * 2 * 3)

再将所有的结果相乘得到的数一定是的倍数。这里可以拿small case验证一下：

factor(210) = 2 * 3 * 5 * 7
factor(lcm((p-1)*(q-1)) = 2 * 3 * 5 * 7 * 11 * 31 * 43 * 71 * 211
factor(11-1)=2 * 5
factor(31-1)=2 * 3 * 5
factor(43-1)=2 * 3 * 7
factor(71-1)=2 * 5 * 7
factor(211-1)=2 * 3 * 5 * 7

得到t之后再求出，就能得到flag了

exp

import itertools
from Crypto.Util.number import long_to_bytes,isPrime
from math import prod

# From the itertools documentation/example
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s)+1))

# From factordb
factors = [2, 3, 5, 17, 257, 641, 65537, 274177, 2424833, 6700417, 67280421310721, 1238926361552897, 59649589127497217, 5704689200685129054721, 7455602825647884208337395736200454918783366342657, 93461639715357977769163558199606896584051237541638188580280321, 741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737]

assert 2**1025-2 == prod(factors)

C = []
for ps in powerset(factors):
    v = prod(ps) + 1
    if isPrime(v):
        C.append(prod(ps) + 1)
res = prod(C)

e = 65537
n = 0x99efa9177387907eb3f74dc09a4d7a93abf6ceb7ee102c689ecd0998975cede29f3ca951feb5adfb9282879cc666e22dcafc07d7f89d762b9ad5532042c79060cdb022703d790421a7f6a76a50cceb635ad1b5d78510adf8c6ff9645a1b179e965358e10fe3dd5f82744773360270b6fa62d972d196a810e152f1285e0b8b26f5d54991d0539a13e655d752bd71963f822affc7a03e946cea2c4ef65bf94706f20b79d672e64e8faac45172c4130bfeca9bef71ed8c0c9e2aa0a1d6d47239960f90ef25b337255bac9c452cb019a44115b0437726a9adef10a028f1e1263c97c14a1d7cd58a8994832e764ffbfcc05ec8ed3269bb0569278eea0550548b552b1
ct = 0x339be515121dab503106cd190897382149e032a76a1ca0eec74f2c8c74560b00dffc0ad65ee4df4f47b2c9810d93e8579517692268c821c6724946438a9744a2a95510d529f0e0195a2660abd057d3f6a59df3a1c9a116f76d53900e2a715dfe5525228e832c02fd07b8dac0d488cca269e0dbb74047cf7a5e64a06a443f7d580ee28c5d41d5ede3604825eba31985e96575df2bcc2fefd0c77f2033c04008be9746a0935338434c16d5a68d1338eabdcf0170ac19a27ec832bf0a353934570abd48b1fe31bc9a4bb99428d1fbab726b284aec27522efb9527ddce1106ba6a480c65f9332c5b2a3c727a2cca6d6951b09c7c28ed0474fdc6a945076524877680

d = pow(e, -1, res)
print(long_to_bytes(int(pow(ct, d, n))))

b'CTF{Recycling_Is_Great}'

记一下exp中itertools的两个函数

itertools.combinations(iterable, r)方法可以创建一个迭代器，返回iterable中所有长度为r的子序列，返回的子序列中的项按输入iterable中的顺序排序
example:
list1 = [1,2,3,4]
list2 = list(itertools.combinations(list1,3))
output:
list2 = [(1,2,3), (1,2,4), (1,3,4), (2,3,4)]

itertools.chain.from_iterable(iterables)可以将多个迭代器连接成一个同一的迭代器
example:
list1 = [(1,2),(1,3)]
list2 = list(itertools.chain.from_iterable(list1))
output:
list2 = [1, 2, 1, 3]

Canzik's Blog

GoogleCTF2022 复现(更新中)

CYCLING