AlpacaHack Round 3 : Rainbow Sweet Alchemist

[roaris]

https://alpacahack.com/challenges/rainbow-sweet-alchemist

[roaris]

RSA暗号の問題 $p, q$ の生成方法が特殊である

1. 16個の素数を用意する
2. 2*(16個の素数の総積)+1を計算
3. 2の結果が素数なら、これを利用
4. 2の結果が素数でないなら、16個の素数から1つを削除し、新たに1つ素数を追加し、2に戻る

1で用意される素数、4で追加される素数は、deterministicGetPrimeという関数で生成されていて、乱数シードが固定されているので、生成される素数が分かっている しかし、4で削除される素数は、何が削除されるのか分からない

import os
import random
from math import prod
from Crypto.Util.number import isPrime, bytes_to_long

r = random.Random(0)
def deterministicGetPrime():
  while True:
    if isPrime(p := r.getrandbits(64)):
      return p

# This is not likely to fail
assert deterministicGetPrime() == 2710959347947821323, "Your Python's random module is not compatible with this challenge."

def getPrime(bit):
  factors = [deterministicGetPrime() for _ in range(bit // 64)]
  while True:
    p = 2 * prod(factors) + 1
    if isPrime(p):
      return p
    factors.remove(random.choice(factors))
    factors.append(deterministicGetPrime())

flag = os.environ.get("FLAG", "fakeflag").encode()
m = bytes_to_long(flag)

p, q = getPrime(1024), getPrime(1024)
n = p * q
e = 0x10001
c = pow(m, e, n)

print(f"{n=}")
print(f"{e=}")
print(f"{c=}")

[roaris]

$p-1$ 法の説明を読んでいたら解法を思いついた

deterministicGetPrime によって生成される素数の列を $g_1, g_2\ldots,g_x$ とする 適当な素数 $a$ を用意し、 $a^{2g_1g_2\ldots g_x}$ を考える $a$ は $p$ と互いに素なら何でも良い(つまり $p$ でなければ何でも良い)

$x$ が十分大きければ $2g_1g_2\ldots g_x$ は $p-1$ の倍数であり $2g_1g_2\ldots g_x = (p-1)k$ と表せる よって $\mod p$ において $a^{2g_1g_2\ldots g_x} = a^{(p-1)k} = 1$ である (フェルマーの小定理を使っている) $a^{2g_1g_2\ldots g_x}-1$ は $p$ の倍数なので、 $gcd(a^{2g_1g_2\ldots g_x}-1, n) = p$ となる

$x$を大きくしすぎると $a^{2g_1g_2\ldots g_x}-1$ が $q$ の倍数にもなり、 $gcd(a^{2g_1g_2\ldots g_x}-1, n) = n$ となってしまうことに注意 $x = 300$ で上手くいくことが分かった

import random
from math import gcd
from Crypto.Util.number import isPrime, long_to_bytes

r = random.Random(0)
def deterministicGetPrime():
  while True:
    if isPrime(p := r.getrandbits(64)):
      return p

n=2350478429681099659482802009772446082018100644248516135321613920512468478639125995627622723613436514363575959981129347545346377683616601997652559989194209421585293503204692287227768734043407645110784759572198774750930099526115866644410725881688186477790001107094553659510391748347376557636648685171853839010603373478663706118665850493342775539671166315233110564897483927720435690486237018231160348429442602322737086330061842505643074752650924036094256703773247700173034557490511259257339056944624783261440335003074769966389878838392473674878449536592166047002406250295311924149998650337286245273761909
e=65537
c=945455686374900611982512983855180418093086799652768743864445887891673833536194784436479986018226808021869459762652060495495939514186099959619150594580806928854502608487090614914226527710432592362185466014910082946747720345943963459584430804168801787831721882743415735573097846726969566369857274720210999142004037914646773788750511310948953348263288281876918925575402242949315439533982980005949680451780931608479641161670505447003036276496409290185385863265908516453044673078999800497412772426465138742141279302235558029258772175141248590241406152365769987248447302410223052788101550323890531305166459

a = 2
x = 300
M = 2

for _ in range(x):
    M *= deterministicGetPrime()

p = gcd(pow(a, M, n) - 1, n)
assert(p != 1)
assert(p != n)
q = n // p
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
print(long_to_bytes(pow(c, d, n)).decode())

[roaris]

コンテスト中は $a^{2g_1g_2\ldots g_x}$ ではなく $a^{g_1g_2\ldots g_x}$ を考えていた $\mod p$ において $a^{g_1g_2\ldots g_x} = a^{\frac{(p-1)k}{2}} = ((a^{p-1})^k)^{\frac{1}{2}} = 1$ という式変形をしていたのだが、この式変形は間違っていて $a^{g_1g_2\ldots g_x} - 1$ が $p$ の倍数になるとは限らない 式変形が間違っている理由は、あまり理解してない 合同式において平方根を取ることは出来ないから？ 平方根を取ることが出来ないのは $a^\frac{1}{2}$ を $\mod p$ において $x x = a$ を満たす $x$ として、このような $x$ は存在しないかもしれないため？ それとも $x$ が複数存在するかもしれないため？ 例えば $x x = 1$ を満たす $x$ は $1, p-1$ の少なくとも2つはある

[roaris]

もう1つ解法がある

$x$が十分に大きければ $4g_1g_2\ldots g_x = (p-1)(q-1)k$ である 秘密鍵は $\mod (p-1)(q-1)$ において $ed = 1$ を満たす $d$ だが $\mod (p-1)(q-1)$ の代わりに $\mod (p-1)(q-1)k$ を使っても良い $\mod (p-1)(q-1)k$ において $ed = 1$ を満たす $d$ は $\mod (p-1)(q-1)$ において $ed = 1$ も満たすためである

import random
from Crypto.Util.number import isPrime, long_to_bytes

r = random.Random(0)
def deterministicGetPrime():
  while True:
    if isPrime(p := r.getrandbits(64)):
      return p

n=2350478429681099659482802009772446082018100644248516135321613920512468478639125995627622723613436514363575959981129347545346377683616601997652559989194209421585293503204692287227768734043407645110784759572198774750930099526115866644410725881688186477790001107094553659510391748347376557636648685171853839010603373478663706118665850493342775539671166315233110564897483927720435690486237018231160348429442602322737086330061842505643074752650924036094256703773247700173034557490511259257339056944624783261440335003074769966389878838392473674878449536592166047002406250295311924149998650337286245273761909
e=65537
c=945455686374900611982512983855180418093086799652768743864445887891673833536194784436479986018226808021869459762652060495495939514186099959619150594580806928854502608487090614914226527710432592362185466014910082946747720345943963459584430804168801787831721882743415735573097846726969566369857274720210999142004037914646773788750511310948953348263288281876918925575402242949315439533982980005949680451780931608479641161670505447003036276496409290185385863265908516453044673078999800497412772426465138742141279302235558029258772175141248590241406152365769987248447302410223052788101550323890531305166459

x = 1000
M = 4

for _ in range(x):
    M *= deterministicGetPrime()

d = pow(e, -1, M)
print(long_to_bytes(pow(c, d, n)).decode())