More than 1 year has passed since last update.

ACSC 2023 (Crypto) Writeup

Last updated at 2023-03-05Posted at 2023-03-03

Merkle Hellman

暗号化には長さ 7 の配列 b が使われている
フラッグの各文字について，先頭ビット以外のビットが 1 なら b[i] を足す
普通に総当たりしても，フラッグの長さを $n$ として，$O(n \cdot 2^7 \cdot 7)$ しかかからない
効率的にするなら，予めすべての文字を暗号化しておく ($O(2^7 \cdot 7 + 7n)$)

b = [7352, 2356, 7579, 19235, 1944, 14029, 1084]
# Private Key = ([184, 332, 713, 1255, 2688, 5243, 10448], 20910)
ct = [8436, 22465, 30044, 22465, 51635, 10380, 11879, 50551, 35250, 51223, 14931, 25048, 7352, 50551, 37606, 39550]

dic = dict()
for f in range(2**7):
    s = 0
    for i in range(7):
        if f & (64>>i):
            s += b[i]
    dic[s] = chr(f)

flag = ''
for c in ct:
    flag += dic[c]
print(flag)

Check_number_63

$n$ (2048 bit) を素因数分解した値が FLAG
$65537 \le e < 66173$ を満たす素数 $e$ に対する $c_i = \frac{e_i \cdot d_i - 1}{\phi}$ が与えられる ($\phi = (p-1)(q-1), d_i = e_i^{-1} \pmod \phi$)
$a = p + q$ とすると，$c_i = \frac{e_i \cdot d_i - 1}{\phi}$ から $c_i (n - a - 1) = e_i \cdot d_i - 1$
法を $e_i$ として $a = n - 1 + c_i^{-1}$ とできる
中国式剰余定理を使うとすべての $i$ について成り立つような $a$ が求められる (この段階ではすべての $i$ について成り立つだけで $a = p + q$ となるような $a$ が求まるかどうかはわからない)
ただし，それらの式を満たす他の $a'$ は $a' = a + k \cdot \Pi e_i$ で求められる
$a^2 - 4 n = p^2 + 2pq +q^2 - 4pq = (p - q)^2$ となるので $a$ が平方数となるかどうかで確認できる
これで $p \cdot q$ と $p + q$ がわかっているので，二次方程式の解と係数の関係から $p, q = \frac{(p+q) \pm \sqrt{(p+q)^2 - 4pq}}{2}$ で求められる
(Sage を使う)

from hashlib import sha512
from Crypto.Util.number import *
import math
n = 24575303335152579483219397187273958691356380033536698304119157688003502052393867359624475789987237581184979869428436419625817866822376950791646781307952833871208386360334267547053595730896752931770589720203939060500637555186552912818531990295111060561661560818752278790449531513480358200255943011170338510477311001482737373145408969276262009856332084706260368649633253942184185551079729283490321670915209284267457445004967752486031694845276754057130676437920418693027165980362069983978396995830448343187134852971000315053125678630516116662920249232640518175555970306086459229479906220214332209106520050557209988693711

ln = open('./Check_number_63/output.txt').readlines()[1:]
es = []
cs = []
for l in ln:
    e, c = l.replace('\n','').split(':')
    es.append(int(e))
    cs.append(int(c))

xs = [(n + 1 + inverse(c, e)) % e for c, e in zip(cs, es)]
mods = es
a = crt(xs, mods)

prd_es = math.prod(es)
for i in range(100000):
    a += prd_es
    if is_square(a^2 - 4 * n):
        break

phi = n - a + 1

for e, c in zip(es, cs):
    d = inverse(e, phi)
    check_number = (e*d - 1) // phi
    assert c == check_number
    assert (e*d - 1) % phi == 0

sq = int(sqrt(a**2 - 4 * n))
print(sq)
p = (a + sq)//2
q = n // p

print('p:', p)
print('q :', q)

assert p * q == n
if p > q:p,q = q,p
flag = "ACSC{" + sha512( f"{p}{q}".encode() ).hexdigest() + "}"
print(flag)

Dual Signature Algorithm

Digital Signature Algorithm ... Elgamal 暗号から派生した署名アルゴリズム
- ただし，今回は $r = (g^k \mod p) \mod q$ が $r = g^k \mod p$ となっていて実装に不備がある
- (実装に不備がなくても解けるから関係はない)
同一のメッセージ，秘密鍵 $x$ に対する実装に不備のある二種類パラメータの DSA から秘密鍵 $x$ を特定すれば FLAG が得られる
$s_1, s_2$ についての式から以下のように変形する
- $r_1 x - s_1 k + q_1 l_1 + z = 0$
- $r_2 x - s_2 k + q_2 l_2 + z = 0$
- 既知な変数
  - $r_1, r_2$ (521 bit)
  - $ s_1, s_2$ (521 bit)
  - $q_1, q_2$ (521 bit)
  - $z$ (255 bit)
- 未知な変数
  - $x$ (504 bit)
  - $k$ (512 bit)
  - $l_1, l_2$ (?)

LLL で解けそう

(x, k, l_1, l_2, 1)
\begin{pmatrix}
r_1 & r_2 & 2^8 & 0 & 0 \\
-s_1 & -s_2 & 0 & 1 & 0 \\
q_1 & 0 & 0 & 0 & 0 \\
0 & q_2 & 0 & 0 & 0 \\
z & z & 0 & 0 & 2^{512} \\
\end{pmatrix}
= (r_1 x - s_1 k + q_1 l_1 + z, r_2 x - s_2 k + q_2 l_2 + z, 2^8 x, k, 2^{512})

Sage で解く

from hashlib import sha256
from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger, inverse, long_to_bytes

g = 4
p1, p2 = 6276170351477662358610296265757659534898563584329624403861678676207084984210281982964595245398676819568696602458985212398017251665201155991266054305219383699, 6592790035600261324619481304533463005761130886111654202136347967085156073379713687101783875841638513262245459729322943177912713281466956529743757383039213839
y1, y2 = 4402230695629594751098609664164747722309480897222957264699530671849221909102875035849237359507796750078710393158944361439911537205013148370997499859214033074, 1681962252704346790535503180583651281903938541944441796556533586799974913619493902209110690623728835694029912753819263510084101226503501626563053650880055759
m = b'omochi mochimochi mochimochi omochi'
r1, s1 = (2059408995750136677433298244389263055046695445249968690077607175900623237060138734944126780231327500254319039236115174790677322287273023749694890125234033630, 705204023016308665771881112578269844527040578525414513229064579516151996129198705744493237004425745778721444958494868745594673773644781132717640592278534802)
r2, s2 = (3246603518972133458487019157522113455602145970917894172952170087044203882577925192461339870709563972992589487629762432781841010769867505736764230484818447604, 2142497127325776381345617721109438439759390966544000203818908086062572965004742554536684765731611856029799528558073686810627789363181741779462572364133421373)

q1 = (p1-1)//2
q2 = (p2-1)//2

def h(m: bytes) -> int:
    return int(sha256(m).hexdigest(), 16)

z = h(m)
N = 2^(2^10)
mat = [
    [r1, r2, 2^8, 0, 0],
    [-s1, -s2, 0, 1, 0],
    [q1, 0, 0, 0, 0],
    [0, q2, 0, 0, 0],
    [z, z, 0, 0, 2^512]
    ]
for i in range(len(mat)):
    mat[i][0] *= N
    mat[i][1] *= N

ans = matrix(ZZ, mat).LLL()
for a in ans:
    if a[0] == 0 and a[1] == 0 and a[-1] == 2^512 and a[2] % (2^8) == 0:
        x = a[2] //(2^8)
        break

print(long_to_bytes(x))

Corrupted

corrupted.pem が与えられている

-----BEGIN RSA PRIVATE KEY-----
MIIEpAIBAAKCAQEAn+8Rj11c2JOgyf6s1Hiiwt553hw9+oGcd1EGo8H5tJOEiUnP
NixaIGMK1O7CU7+IEe43PJcGPPkCti2kz5qAXAyXXBMAlHF46spmQaQFpVRRVMZD
1yInh0QXEjgBBFZKaH3VLh9FpCKYpfqij+OlphoSHlfc7l2Wfct40TDFg13WdpVB
BseCEmaY/b+kxwdfVe7Dzt8kd2ASPuNbOqKvv8ijTgiqpsX5uinjvr/3/srINm8X
xpANqO/eSXP8kO4abOJtyfg2bWvO9QvQRaUIjnYioAkyiqcttbzGIekCfktlA+Rn
JLL19tEG43hubOZAwqGDxvXfKEKx9E2Yx4Da/wIDAQA?AoI?????8S??Om/???xN
3c??0?/G?OO?aQWQB??ECCi??KD?w??2mFc??pTM?r?rX??X+XFW??Rtw?o?d????ZQ?yp?mczG?q2?0O???1o3?Jt?8?+00s?SY+??MG??7d??7k??o?????ci?K??????wK??Y??gqV????9????YA?Hh5T????ICP+?3HTU?l???m0y?6??2???b2x???????+7??T????????n?7????b?P??iL?/???tq???5jLuy??lX?d?ZEO?7???ld???g
?r?rK??IYA???0???zYCIZt2S???cP??W????f???l5?3c+??UkJr4E?QH??PiiD
WLB???f5A?G?A???????????u???3?K???????I???S?????????J?p?3?N?W???
????r???????8???o???m?????8?s???1?4?l?T?3?j?y?6?F?c?g?3?A?8?S?1?
X?o?D?C?+?7?F?V?U?1?f?K?a?F?7?S?b?V?/?v?5?1?V?A?5?G?y?X?AoGB?L?i
?2?C?t?W?s?Z?h?L?t?3?r?d?M?s?U?E?L?P?n?2?U?G?M?g?D?u?E?s?a?h?K?m
?9?/?n?o?J?8?e?9?9?k?N?2?l?T?8?k?b?e?j?n?Q?u?z?z?e?A?S?6?0?w?5?0
?B?V?i?s?R?W?6?Y?6?u?l?s?G?c?Q?2?Q?w?U?l??GA??V?f???kVYfl???WyY?
3J?2fF?h/???UqfpeO???o?k?9kF??a8L?V?w??????J??9?iP????D???JSx??g??IUC0??t7???I??c??????eh/No?????y8???0?E+??1?JC?Oj??HFy??2T?1nV??HH?+???+??s?L?o??K?zc?????BhB2A?????E??b???e?f??KruaZ??u?tp?Tq?c?t?????iQ1qS??h??m?S?/????FDu3i?p???S??Q?o??0s?e0?n?Hv??C?CnM?/Dw
m9?????uC?Ktm????D?e????h7?A??V??O??5/XsY??Y?A???????q?y?gk?Pbq?
????MQK?gQ??SQ?????ERjLp?N??A??P?So?TPE??WWG???lK?Q????o?aztnUT?
eKe4+h0?VkuB?b?v?7ge?nK1??Jy7?y??9??????BP??gG?kKK?y?Z???yES4i??
?Uhc?p????c4ln?m?r???P??C?8?X?d??TP??k??B?dwjN7??ui?K????????-?N? ?S? ?RI?A?? KE?-???-

PEM ファイルなので，ASN.1 のバイナリデータを Base64 で符号化したもの
今回のファイルの中身は RSA の秘密鍵
改行されていないところは ? が改行文字と考えられる (各行の文字数も一致する)

ASN.1 のフォーマット
- "型 - 長さ - 値" の繰り返しで構成されている
- 型
  - 先頭の 0x30 は SEQUENCE を意味している
  - 0x20 は INTEGER
- 長さ
  - 後ろに続く値の合計バイト数を表す
  - 短形式 (Short form) と長形式 (Long form) がある
    - 短形式 - 長さを表すのは 1 バイトで先頭ビットは必ず 0
      (それ以降に続く値が 0-127 バイトの長さのとき)
    - 長形式 - 最初のバイトの先頭ビットが 1 になっていて，残り 7 ビットが長さフィールド自体のバイト数を表す
      ("型 - 長さの長さ - 長さ - 値" となる)

RSA の形式 (RFC 2313)

RSAPrivateKey ::= SEQUENCE {
    version Version,
    modulus INTEGER, -- n
    publicExponent INTEGER, -- e
    privateExponent INTEGER, -- d
    prime1 INTEGER, -- p
    prime2 INTEGER, -- q
    exponent1 INTEGER, -- d mod (p-1)
    exponent2 INTEGER, -- d mod (q-1)
    coefficient INTEGER -- (inverse of q) mod p }

Version ::= INTEGER

16進数に変換する

from string import printable

pem = '''
MIIEpAIBAAKCAQEAn+8Rj11c2JOgyf6s1Hiiwt553hw9+oGcd1EGo8H5tJOEiUnP
NixaIGMK1O7CU7+IEe43PJcGPPkCti2kz5qAXAyXXBMAlHF46spmQaQFpVRRVMZD
1yInh0QXEjgBBFZKaH3VLh9FpCKYpfqij+OlphoSHlfc7l2Wfct40TDFg13WdpVB
BseCEmaY/b+kxwdfVe7Dzt8kd2ASPuNbOqKvv8ijTgiqpsX5uinjvr/3/srINm8X
xpANqO/eSXP8kO4abOJtyfg2bWvO9QvQRaUIjnYioAkyiqcttbzGIekCfktlA+Rn
JLL19tEG43hubOZAwqGDxvXfKEKx9E2Yx4Da/wIDAQA?AoI?????8S??Om/???xN
3c??0?/G?OO?aQWQB??ECCi??KD?w??2mFc??pTM?r?rX??X+XFW??Rtw?o?d???
ZQ?yp?mczG?q2?0O???1o3?Jt?8?+00s?SY+??MG??7d??7k??o?????ci?K????
?wK??Y??gqV????9????YA?Hh5T????ICP+?3HTU?l???m0y?6??2???b2x?????
?+7??T????????n?7????b?P??iL?/???tq???5jLuy??lX?d?ZEO?7???ld???g
?r?rK??IYA???0???zYCIZt2S???cP??W????f???l5?3c+??UkJr4E?QH??PiiD
WLB???f5A?G?A???????????u???3?K???????I???S?????????J?p?3?N?W???
????r???????8???o???m?????8?s???1?4?l?T?3?j?y?6?F?c?g?3?A?8?S?1?
X?o?D?C?+?7?F?V?U?1?f?K?a?F?7?S?b?V?/?v?5?1?V?A?5?G?y?X?AoGB?L?i
?2?C?t?W?s?Z?h?L?t?3?r?d?M?s?U?E?L?P?n?2?U?G?M?g?D?u?E?s?a?h?K?m
?9?/?n?o?J?8?e?9?9?k?N?2?l?T?8?k?b?e?j?n?Q?u?z?z?e?A?S?6?0?w?5?0
?B?V?i?s?R?W?6?Y?6?u?l?s?G?c?Q?2?Q?w?U?l??GA??V?f???kVYfl???WyY?
3J?2fF?h/???UqfpeO???o?k?9kF??a8L?V?w??????J??9?iP????D???JSx??g
?IUC0??t7???I??c??????eh/No?????y8???0?E+??1?JC?Oj??HFy??2T?1nV?
HH?+???+??s?L?o??K?zc?????BhB2A?????E??b???e?f??KruaZ??u?tp?Tq?c
t?????iQ1qS??h??m?S?/????FDu3i?p???S??Q?o??0s?e0?n?Hv??C?CnM?/Dw
m9?????uC?Ktm????D?e????h7?A??V??O??5/XsY??Y?A???????q?y?gk?Pbq?
????MQK?gQ??SQ?????ERjLp?N??A??P?So?TPE??WWG???lK?Q????o?aztnUT?
eKe4+h0?VkuB?b?v?7ge?nK1??Jy7?y??9??????BP??gG?kKK?y?Z???yES4i??
?Uhc?p????c4ln?m?r???P??C?8?X?d??TP??k??B?dwjN7??ui?K????????
'''

pem = pem.replace('\n','')

b64_enc = printable[10+26:10+52] + printable[10:10+26] + printable[:10] + '+/'
b64_dec = dict()
for i in range(64):
    b64_dec[b64_enc[i]] = i

bits = ''
for p in pem:
    if p == '?':
        bits += '?'*6
    else:
        bits += format(b64_dec[p], '06b')

bb = []
bib = []

bs = ''
cnt = 0
f1 = ''
f2 = ''
for i in range(0, len(bits)-8, 8):
    byte = bits[i:i+8]
    u = '?' if '?' in byte[:4] else hex(int(byte[:4], 2))[2:]
    l = '?' if '?' in byte[4:] else hex(int(byte[4:], 2))[2:]
    f1 += f'{byte} '
    f2 += f'{u}{l} '
    if cnt % 4 == 3:
        print('{:3x}'.format(cnt-3), ':', f1, ':', f2)
        f1 = ''
        f2 = ''
    cnt += 1
    bb.append(f'{u}{l}')
    bib.append(byte)

  0 : 00110000 10000010 00000100 10100100  : 30 82 04 a4 
  4 : 00000010 00000001 00000000 00000010  : 02 01 00 02 
  8 : 10000010 00000001 00000001 00000000  : 82 01 01 00 
  c : 10011111 11101111 00010001 10001111  : 9f ef 11 8f 
 10 : 01011101 01011100 11011000 10010011  : 5d 5c d8 93 
 14 : 10100000 11001001 11111110 10101100  : a0 c9 fe ac 
 18 : 11010100 01111000 10100010 11000010  : d4 78 a2 c2 
 1c : 11011110 01111001 11011110 00011100  : de 79 de 1c 
 20 : 00111101 11111010 10000001 10011100  : 3d fa 81 9c 
 24 : 01110111 01010001 00000110 10100011  : 77 51 06 a3 
 28 : 11000001 11111001 10110100 10010011  : c1 f9 b4 93 
 2c : 10000100 10001001 01001001 11001111  : 84 89 49 cf 
 30 : 00110110 00101100 01011010 00100000  : 36 2c 5a 20 
 34 : 01100011 00001010 11010100 11101110  : 63 0a d4 ee 
 38 : 11000010 01010011 10111111 10001000  : c2 53 bf 88 
 3c : 00010001 11101110 00110111 00111100  : 11 ee 37 3c 
 40 : 10010111 00000110 00111100 11111001  : 97 06 3c f9 
 44 : 00000010 10110110 00101101 10100100  : 02 b6 2d a4 
 48 : 11001111 10011010 10000000 01011100  : cf 9a 80 5c 
 4c : 00001100 10010111 01011100 00010011  : 0c 97 5c 13 
 50 : 00000000 10010100 01110001 01111000  : 00 94 71 78 
 54 : 11101010 11001010 01100110 01000001  : ea ca 66 41 
 58 : 10100100 00000101 10100101 01010100  : a4 05 a5 54 
 5c : 01010001 01010100 11000110 01000011  : 51 54 c6 43 
 60 : 11010111 00100010 00100111 10000111  : d7 22 27 87 
 64 : 01000100 00010111 00010010 00111000  : 44 17 12 38 
 68 : 00000001 00000100 01010110 01001010  : 01 04 56 4a 
 6c : 01101000 01111101 11010101 00101110  : 68 7d d5 2e 
 70 : 00011111 01000101 10100100 00100010  : 1f 45 a4 22 
 74 : 10011000 10100101 11111010 10100010  : 98 a5 fa a2 
 78 : 10001111 11100011 10100101 10100110  : 8f e3 a5 a6 
 7c : 00011010 00010010 00011110 01010111  : 1a 12 1e 57 
 80 : 11011100 11101110 01011101 10010110  : dc ee 5d 96 
 84 : 01111101 11001011 01111000 11010001  : 7d cb 78 d1 
 88 : 00110000 11000101 10000011 01011101  : 30 c5 83 5d 
 8c : 11010110 01110110 10010101 01000001  : d6 76 95 41 
 90 : 00000110 11000111 10000010 00010010  : 06 c7 82 12 
 94 : 01100110 10011000 11111101 10111111  : 66 98 fd bf 
 98 : 10100100 11000111 00000111 01011111  : a4 c7 07 5f 
 9c : 01010101 11101110 11000011 11001110  : 55 ee c3 ce 
 a0 : 11011111 00100100 01110111 01100000  : df 24 77 60 
 a4 : 00010010 00111110 11100011 01011011  : 12 3e e3 5b 
 a8 : 00111010 10100010 10101111 10111111  : 3a a2 af bf 
 ac : 11001000 10100011 01001110 00001000  : c8 a3 4e 08 
 b0 : 10101010 10100110 11000101 11111001  : aa a6 c5 f9 
 b4 : 10111010 00101001 11100011 10111110  : ba 29 e3 be 
 b8 : 10111111 11110111 11111110 11001010  : bf f7 fe ca 
 bc : 11001000 00110110 01101111 00010111  : c8 36 6f 17 
 c0 : 11000110 10010000 00001101 10101000  : c6 90 0d a8 
 c4 : 11101111 11011110 01001001 01110011  : ef de 49 73 
 c8 : 11111100 10010000 11101110 00011010  : fc 90 ee 1a 
 cc : 01101100 11100010 01101101 11001001  : 6c e2 6d c9 
 d0 : 11111000 00110110 01101101 01101011  : f8 36 6d 6b 
 d4 : 11001110 11110101 00001011 11010000  : ce f5 0b d0 
 d8 : 01000101 10100101 00001000 10001110  : 45 a5 08 8e 
 dc : 01110110 00100010 10100000 00001001  : 76 22 a0 09 
 e0 : 00110010 10001010 10100111 00101101  : 32 8a a7 2d 
 e4 : 10110101 10111100 11000110 00100001  : b5 bc c6 21 
 e8 : 11101001 00000010 01111110 01001011  : e9 02 7e 4b 
 ec : 01100101 00000011 11100100 01100111  : 65 03 e4 67 
 f0 : 00100100 10110010 11110101 11110110  : 24 b2 f5 f6 
 f4 : 11010001 00000110 11100011 01111000  : d1 06 e3 78 
 f8 : 01101110 01101100 11100110 01000000  : 6e 6c e6 40 
 fc : 11000010 10100001 10000011 11000110  : c2 a1 83 c6 
100 : 11110101 11011111 00101000 01000010  : f5 df 28 42 
104 : 10110001 11110100 01001101 10011000  : b1 f4 4d 98 
108 : 11000111 10000000 11011010 11111111  : c7 80 da ff 
10c : 00000010 00000011 00000001 00000000  : 02 03 01 00 
110 : 00?????? 00000010 10000010 00??????  : ?? 02 82 ?? 
114 : ???????? ???????? ???????? 11110001  : ?? ?? ?? f1 
118 : 0010???? ???????? 00111010 01101111  : 2? ?? 3a 6f 
11c : 11?????? ???????? ????1100 01001101  : ?? ?? ?c 4d 
120 : 11011101 1100???? ???????? 110100??  : dd c? ?? d? 
124 : ????1111 11000110 ??????00 11100011  : ?f c6 ?? e3 
128 : 10?????? 01101001 00000101 10010000  : ?? 69 05 90 
12c : 000001?? ???????? ??000100 00001000  : 0? ?? ?4 08 
130 : 00101000 10?????? ??????00 10100000  : 28 ?? ?? a0 
134 : 11?????? 110000?? ???????? ??110110  : ?? c? ?? ?6 
138 : 10011000 01010111 00?????? ??????10  : 98 57 ?? ?? 
13c : 10010100 11001100 ??????10 1011????  : 94 cc ?? b? 
140 : ??101011 010111?? ???????? ??010111  : ?b 5? ?? ?7 
144 : 11111001 01110001 01010110 ????????  : f9 71 56 ?? 
148 : ????0100 01101101 110000?? ????1010  : ?4 6d c? ?a 
14c : 00?????? 011101?? ???????? ????????  : ?? 7? ?? ?? 
150 : 01100101 0000???? ??110010 101001??  : 65 0? ?2 a? 
154 : ????1001 10011100 11001100 0110????  : ?9 9c cc 6? 
158 : ??101010 110110?? ????1101 00001110  : ?a d? ?d 0e 
15c : ???????? ???????? ??110101 10100011  : ?? ?? ?5 a3 
160 : 0111???? ??001001 101101?? ????1111  : 7? ?9 b? ?f 
164 : 00?????? 11111011 01001101 00101100  : ?? fb 4d 2c 
168 : ??????01 00100110 00111110 ????????  : ?? 26 3e ?? 
16c : ????0011 00000110 ???????? ????1110  : ?3 06 ?? ?e 
170 : 11011101 ???????? ????1110 11100100  : dd ?? ?e e4 
174 : ???????? ????1010 00?????? ????????  : ?? ?a ?? ?? 
178 : ???????? ???????? 01110010 0010????  : ?? ?? 72 2? 
17c : ??001010 ???????? ???????? ????????  : ?a ?? ?? ?? 
180 : ??????11 00000010 10?????? ??????01  : ?? 02 ?? ?? 
184 : 1000???? ???????? 10000010 10100101  : 8? ?? 82 a5 
188 : 01?????? ???????? ???????? ??111101  : ?? ?? ?? ?d 
18c : ???????? ???????? ???????? 01100000  : ?? ?? ?? 60 
190 : 0000???? ??000111 10000111 10010100  : 0? ?7 87 94 
194 : 11?????? ???????? ???????? ??001000  : ?? ?? ?? ?8 
198 : 00001000 11111111 10?????? 11011100  : 08 ff ?? dc 
19c : 01110100 11010100 ??????10 0101????  : 74 d4 ?? 5? 
1a0 : ???????? ??????10 01101101 00110010  : ?? ?? 6d 32 
1a4 : ??????11 1010???? ???????? 110110??  : ?? a? ?? d? 
1a8 : ???????? ???????? 01101111 01101100  : ?? ?? 6f 6c 
1ac : 01?????? ???????? ???????? ????????  : ?? ?? ?? ?? 
1b0 : ??????11 11101110 11?????? ??????01  : ?? ee ?? ?? 
1b4 : 0011???? ???????? ???????? ????????  : 3? ?? ?? ?? 
1b8 : ???????? ???????? ????1001 11??????  : ?? ?? ?9 ?? 
1bc : 111011?? ???????? ???????? ??????01  : e? ?? ?? ?? 
1c0 : 1011???? ??001111 ???????? ????1000  : b? ?f ?? ?8 
1c4 : 10001011 ??????11 1111???? ????????  : 8b ?? f? ?? 
1c8 : ??????10 11011010 10?????? ????????  : ?? da ?? ?? 
1cc : ????1110 01100011 00101110 11101100  : ?e 63 2e ec 
1d0 : 10?????? ??????10 01010101 11??????  : ?? ?? 55 ?? 
1d4 : 011101?? ????0110 01000100 001110??  : 7? ?6 44 3? 
1d8 : ????1110 11?????? ???????? ????1001  : ?e ?? ?? ?9 
1dc : 01011101 ???????? ???????? ??100000  : 5d ?? ?? ?0 
1e0 : ??????10 1011???? ??101011 001010??  : ?? b? ?b 2? 
1e4 : ???????? ??001000 01100000 0000????  : ?? ?8 60 0? 
1e8 : ???????? ??????11 0100???? ????????  : ?? ?? 4? ?? 
1ec : ??????11 00110110 00000010 00100001  : ?? 36 02 21 
1f0 : 10011011 01110110 010010?? ????????  : 9b 76 4? ?? 
1f4 : ???????? 01110000 1111???? ????????  : ?? 70 f? ?? 
1f8 : 010110?? ???????? ???????? ??????01  : 5? ?? ?? ?? 
1fc : 1111???? ???????? ??????10 01011110  : f? ?? ?? 5e 
200 : 01?????? 11011101 11001111 10??????  : ?? dd cf ?? 
204 : ??????01 01001001 00001001 10101111  : ?? 49 09 af 
208 : 10000001 00?????? 01000000 0111????  : 81 ?? 40 7? 
20c : ???????? 00111110 00101000 10000011  : ?? 3e 28 83 
210 : 01011000 10110000 01?????? ????????  : 58 b0 ?? ?? 
214 : ????0111 11111001 000000?? ????0001  : ?7 f9 0? ?1 
218 : 10?????? 000000?? ???????? ????????  : ?? 0? ?? ?? 
21c : ???????? ???????? ???????? ????????  : ?? ?? ?? ?? 
220 : ???????? ???????? 101110?? ????????  : ?? ?? b? ?? 
224 : ???????? 110111?? ????0010 10??????  : ?? d? ?2 ?? 
228 : ???????? ???????? ???????? ????????  : ?? ?? ?? ?? 
22c : ????0010 00?????? ???????? ????0100  : ?2 ?? ?? ?4 
230 : 10?????? ???????? ???????? ????????  : ?? ?? ?? ?? 
234 : ???????? ???????? ???????? 001001??  : ?? ?? ?? 2? 
238 : ????1010 01?????? 110111?? ????0011  : ?a ?? d? ?3 
23c : 01?????? 010110?? ???????? ????????  : ?? 5? ?? ?? 
240 : ???????? ???????? ???????? 101011??  : ?? ?? ?? a? 
244 : ???????? ???????? ???????? ????????  : ?? ?? ?? ?? 
248 : ???????? 111100?? ???????? ????????  : ?? f? ?? ?? 
24c : 101000?? ???????? ???????? 100110??  : a? ?? ?? 9? 
250 : ???????? ???????? ???????? ????1111  : ?? ?? ?? ?f 
254 : 00?????? 101100?? ???????? ????????  : ?? b? ?? ?? 
258 : 110101?? ????1110 00?????? 100101??  : d? ?e ?? 9? 
25c : ????0100 11?????? 110111?? ????1000  : ?4 ?? d? ?8 
260 : 11?????? 110010?? ????1110 10??????  : ?? c? ?e ?? 
264 : 000101?? ????0111 00?????? 100000??  : 1? ?7 ?? 8? 
268 : ????1101 11?????? 000000?? ????1111  : ?d ?? 0? ?f 
26c : 00?????? 010010?? ????1101 01??????  : ?? 4? ?d ?? 
270 : 010111?? ????1010 00?????? 000011??  : 5? ?a ?? 0? 
274 : ????0000 10?????? 111110?? ????1110  : ?0 ?? f? ?e 
278 : 11?????? 000101?? ????0101 01??????  : ?? 1? ?5 ?? 
27c : 010100?? ????1101 01?????? 011111??  : 5? ?d ?? 7? 
280 : ????0010 10?????? 011010?? ????0001  : ?2 ?? 6? ?1 
284 : 01?????? 111011?? ????0100 10??????  : ?? e? ?4 ?? 
288 : 011011?? ????0101 01?????? 111111??  : 6? ?5 ?? f? 
28c : ????1011 11?????? 111001?? ????1101  : ?b ?? e? ?d 
290 : 01?????? 010101?? ????0000 00??????  : ?? 5? ?0 ?? 
294 : 111001?? ????0001 10?????? 110010??  : e? ?1 ?? c? 
298 : ????0101 11?????? 00000010 10000001  : ?5 ?? 02 81 
29c : 10000001 ??????00 1011???? ??100010  : 81 ?? b? ?2 
2a0 : ??????11 0110???? ??000010 ??????10  : ?? 6? ?2 ?? 
2a4 : 1101???? ??010110 ??????10 1100????  : d? ?6 ?? c? 
2a8 : ??011001 ??????10 0001???? ??001011  : ?9 ?? 1? ?b 
2ac : ??????10 1101???? ??110111 ??????10  : ?? d? ?7 ?? 
2b0 : 1011???? ??011101 ??????00 1100????  : b? ?d ?? c? 
2b4 : ??101100 ??????01 0100???? ??000100  : ?c ?? 4? ?4 
2b8 : ??????00 1011???? ??001111 ??????10  : ?? b? ?f ?? 
2bc : 0111???? ??110110 ??????01 0100????  : 7? ?6 ?? 4? 
2c0 : ??000110 ??????00 1100???? ??100000  : ?6 ?? c? ?0 
2c4 : ??????00 0011???? ??101110 ??????00  : ?? 3? ?e ?? 
2c8 : 0100???? ??101100 ??????01 1010????  : 4? ?c ?? a? 
2cc : ??100001 ??????00 1010???? ??100110  : ?1 ?? a? ?6 
2d0 : ??????11 1101???? ??111111 ??????10  : ?? d? ?f ?? 
2d4 : 0111???? ??101000 ??????00 1001????  : 7? ?8 ?? 9? 
2d8 : ??111100 ??????01 1110???? ??111101  : ?c ?? e? ?d 
2dc : ??????11 1101???? ??100100 ??????00  : ?? d? ?4 ?? 
2e0 : 1101???? ??110110 ??????10 0101????  : d? ?6 ?? 5? 
2e4 : ??010011 ??????11 1100???? ??100100  : ?3 ?? c? ?4 
2e8 : ??????01 1011???? ??011110 ??????10  : ?? b? ?e ?? 
2ec : 0011???? ??100111 ??????01 0000????  : 3? ?7 ?? 0? 
2f0 : ??101110 ??????11 0011???? ??110011  : ?e ?? 3? ?3 
2f4 : ??????01 1110???? ??000000 ??????01  : ?? e? ?0 ?? 
2f8 : 0010???? ??111010 ??????11 0100????  : 2? ?a ?? 4? 
2fc : ??110000 ??????11 1001???? ??110100  : ?0 ?? 9? ?4 
300 : ??????00 0001???? ??010101 ??????10  : ?? 1? ?5 ?? 
304 : 0010???? ??101100 ??????01 0001????  : 2? ?c ?? 1? 
308 : ??010110 ??????11 1010???? ??011000  : ?6 ?? a? ?8 
30c : ??????11 1010???? ??101110 ??????10  : ?? a? ?e ?? 
310 : 0101???? ??101100 ??????00 0110????  : 5? ?c ?? 6? 
314 : ??011100 ??????01 0000???? ??110110  : ?c ?? 0? ?6 
318 : ??????01 0000???? ??110000 ??????01  : ?? 0? ?0 ?? 
31c : 0100???? ??100101 ???????? ????0001  : 4? ?5 ?? ?1 
320 : 10000000 ???????? ????0101 01??????  : 80 ?? ?5 ?? 
324 : 011111?? ???????? ???????? 10010001  : 7? ?? ?? 91 
328 : 01010110 00011111 100101?? ????????  : 56 1f 9? ?? 
32c : ???????? 01011011 00100110 00??????  : ?? 5b 26 ?? 
330 : 11011100 1001???? ??110110 01111100  : dc 9? ?6 7c 
334 : 0101???? ??100001 111111?? ????????  : 5? ?1 f? ?? 
338 : ???????? 01010010 10100111 11101001  : ?? 52 a7 e9 
33c : 01111000 1110???? ???????? ??????10  : 78 e? ?? ?? 
340 : 1000???? ??100100 ??????11 11011001  : 8? ?4 ?? d9 
344 : 00000101 ???????? ????0110 10111100  : 05 ?? ?6 bc 
348 : 001011?? ????0101 01?????? 110000??  : 2? ?5 ?? c? 
34c : ???????? ???????? ???????? ????????  : ?? ?? ?? ?? 
350 : ??001001 ???????? ????1111 01??????  : ?9 ?? ?f ?? 
354 : 10001000 1111???? ???????? ????????  : 88 f? ?? ?? 
358 : ????0000 11?????? ???????? ????0010  : ?0 ?? ?? ?2 
35c : 01010010 110001?? ???????? ??100000  : 52 c? ?? ?0 
360 : ??????00 10000101 00000010 110100??  : ?? 85 02 d? 
364 : ???????? ??101101 111011?? ????????  : ?? ?d e? ?? 
368 : ???????? 001000?? ???????? ??011100  : ?? 2? ?? ?c 
36c : ???????? ???????? ???????? ????????  : ?? ?? ?? ?? 
370 : ????0111 10100001 11111100 11011010  : ?7 a1 fc da 
374 : 00?????? ???????? ???????? ????????  : ?? ?? ?? ?? 
378 : 11001011 1100???? ???????? ??????11  : cb c? ?? ?? 
37c : 0100???? ??000100 111110?? ????????  : 4? ?4 f? ?? 
380 : ??110101 ??????00 10010000 10??????  : ?5 ?? 90 ?? 
384 : 00111010 0011???? ???????? 00011100  : 3a 3? ?? 1c 
388 : 01011100 10?????? ??????11 01100100  : 5c ?? ?? 64 
38c : 11?????? 11010110 01110101 01??????  : ?? d6 75 ?? 
390 : 00011100 0111???? ??111110 ????????  : 1c 7? ?e ?? 
394 : ???????? ??111110 ???????? ????1011  : ?? ?e ?? ?b 
398 : 00?????? 001011?? ????1010 00??????  : ?? 2? ?a ?? 
39c : ??????00 1010???? ??110011 011100??  : ?? a? ?3 7? 
3a0 : ???????? ???????? ???????? ????0000  : ?? ?? ?? ?0 
3a4 : 01100001 00000111 01100000 00??????  : 61 07 60 ?? 
3a8 : ???????? ???????? ???????? 000100??  : ?? ?? ?? 1? 
3ac : ???????? ??011011 ???????? ????????  : ?? ?b ?? ?? 
3b0 : ??011110 ??????01 1111???? ????????  : ?e ?? f? ?? 
3b4 : 00101010 10111011 10011010 011001??  : 2a bb 9a 6? 
3b8 : ???????? ??101110 ??????10 11011010  : ?? ?e ?? da 
3bc : 01?????? 01001110 1010???? ??011100  : ?? 4e a? ?c 
3c0 : 101101?? ???????? ???????? ????????  : b? ?? ?? ?? 
3c4 : ????1000 10010000 11010110 10100100  : ?8 90 d6 a4 
3c8 : 10?????? ??????10 0001???? ????????  : ?? ?? 1? ?? 
3cc : 100110?? ????0100 10?????? 111111??  : 9? ?4 ?? f? 
3d0 : ???????? ???????? ??????00 01010000  : ?? ?? ?? 50 
3d4 : 11101110 11011110 0010???? ??101001  : ee de 2? ?9 
3d8 : ???????? ???????? ??010010 ????????  : ?? ?? ?2 ?? 
3dc : ????0100 00?????? 101000?? ????????  : ?4 ?? a? ?? 
3e0 : ??110100 101100?? ????0111 10110100  : ?4 b? ?7 b4 
3e4 : ??????10 0111???? ??000111 101111??  : ?? 7? ?7 b? 
3e8 : ???????? ??000010 ??????00 00101001  : ?? ?2 ?? 29 
3ec : 11001100 ??????11 11110000 11110000  : cc ?? f0 f0 
3f0 : 10011011 1101???? ???????? ????????  : 9b d? ?? ?? 
3f4 : ???????? ??101110 000010?? ????0010  : ?? ?e 0? ?2 
3f8 : 10101101 100110?? ???????? ????????  : ad 9? ?? ?? 
3fc : ??????00 0011???? ??011110 ????????  : ?? 3? ?e ?? 
400 : ???????? ???????? 10000111 1011????  : ?? ?? 87 b? 
404 : ??000000 ???????? ????0101 01??????  : ?0 ?? ?5 ?? 
408 : ??????00 1110???? ???????? 11100111  : ?? e? ?? e7 
40c : 11110101 11101100 011000?? ????????  : f5 ec 6? ?? 
410 : ??011000 ??????00 0000???? ????????  : ?8 ?? 0? ?? 
414 : ???????? ???????? ???????? ??????10  : ?? ?? ?? ?? 
418 : 1010???? ??110010 ??????10 00001001  : a? ?2 ?? 09 
41c : 00?????? 00111101 10111010 10??????  : ?? 3d ba ?? 
420 : ???????? ???????? ???????? 00110001  : ?? ?? ?? 31 
424 : 00000010 10?????? 10000001 0000????  : 02 ?? 81 0? 
428 : ???????? 01001001 0000???? ????????  : ?? 49 0? ?? 
42c : ???????? ???????? ??000100 01000110  : ?? ?? ?4 46 
430 : 00110010 11101001 ??????00 1101????  : 32 e9 ?? d? 
434 : ???????? 000000?? ???????? ??001111  : ?? 0? ?? ?f 
438 : ??????01 00101010 00?????? 01001100  : ?? 2a ?? 4c 
43c : 11110001 00?????? ??????01 01100101  : f1 ?? ?? 65 
440 : 10000110 ???????? ???????? ??100101  : 86 ?? ?? ?5 
444 : 001010?? ????0100 00?????? ????????  : 2? ?4 ?? ?? 
448 : ???????? ??101000 ??????01 10101100  : ?? ?8 ?? ac 
44c : 11101101 10011101 01000100 11??????  : ed 9d 44 ?? 
450 : 01111000 10100111 10111000 11111010  : 78 a7 b8 fa 
454 : 00011101 00?????? 01010110 01001011  : 1d ?? 56 4b 
458 : 10000001 ??????01 1011???? ??101111  : 81 ?? b? ?f 
45c : ??????11 10111000 00011110 ??????10  : ?? b8 1e ?? 
460 : 01110010 10110101 ???????? ????0010  : 72 b5 ?? ?2 
464 : 01110010 111011?? ????1100 10??????  : 72 e? ?c ?? 
468 : ??????11 1101???? ???????? ????????  : ?? d? ?? ?? 
46c : ???????? ???????? 00000100 1111????  : ?? ?? 04 f? 
470 : ???????? 10000000 0110???? ??100100  : ?? 80 6? ?4 
474 : 00101000 1010???? ??110010 ??????01  : 28 a? ?2 ?? 
478 : 1001???? ???????? ??????11 00100001  : 9? ?? ?? 21 
47c : 00010010 11100010 0010???? ????????  : 12 e2 2? ?? 
480 : ??????01 01001000 01011100 ??????10  : ?? 48 5c ?? 
484 : 1001???? ???????? ???????? ????0111  : 9? ?? ?? ?7 
488 : 00111000 10010110 0111???? ??100110  : 38 96 7? ?6 
48c : ??????10 1011???? ???????? ??????00  : ?? b? ?? ?? 
490 : 1111???? ???????? 000010?? ????1111  : f? ?? 0? ?f 
494 : 00?????? 010111?? ????0111 01??????  : ?? 5? ?7 ?? 
498 : ??????01 00110011 11?????? ??????10  : ?? 33 ?? ?? 
49c : 0100???? ???????? 000001?? ????0111  : 4? ?? 0? ?7 
4a0 : 01110000 10001100 11011110 11??????  : 70 8c de ?? 
4a4 : ??????10 11101000 10?????? 001010??  : ?? e8 ?? 2? 
4a8 : ???????? ???????? ???????? ????????  : ?? ?? ?? ??

最初は "30" から始まっているので SEQUENCE を意味していて，次のバイトが "82" なので長さフィールドのバイト数が 2 バイトであることがわかる
長さが "04 a4" となっているので SEQUENCE の長さが 1184 バイトである
次が "02 01 00" で version を示している
8 バイト目からが "02 82 01 01" で始まっているのでこれが $n$
$n$ の長さは 0x101 (= 257) バイトなので 0xb から 0x10b まで
$n$ の値はすべてわかる
0x10c から "02 03" とあるので "01 00 ??" が $e$ で $e = 0x10001$
0x111 から "02 82 ?? ??" とあり， "?? ??" の 2 バイトが長さなので $d$ の長さがわからないが法を $\phi = (p-1)(q-1)$ でとっているので，$n$ と同じくらいかそれより小さくなるはずなので 256 バイトぐらい (0x111 + 4 + 256 = 0x215) で見る
0x216 から "0? ?1 ??" とあるのでここから $p$ と考えられる
($d$ の長さが 257 バイトであることがわかる)
$p$ は $n$ の半分ぐらいのビット数なので 128 バイトぐらい (0x216 + 3 + 128 = 0x299) で見る
0x29a から "02 81 81" とあるのでここから $q$ で 129 バイトであることがわかる
($p$ も 129 バイトであったことがわかる)
0x29a + 3 + 0x81 = 0x31e からは $d \mod {p-1}$ で "?? ?1 80" となっている
0x31e + 3 + 0x80 = 0x3a1 からは $d \mod {q-1}$ で "?? ?? ?0" となっていてほとんどわからないが，おそらく長さは 0x80 であると考えられる
hex(0x3a1 + 3 + 0x80) = 0x424 からは $q^{-1} \mod p$ で "02 ?? 81" となっている
(これで最初の SEQUENCE の長さと一致する)

各パラメータを見てみる

n = bit_form[0x8 + 4:0x8 + 4 + 0x101]
e = bit_form[0x10c + 2:0x10c + 2 + 3]
d = bit_form[0x111 + 4:0x111 + 4 + 257]
p = bit_form[0x216 + 3:0x216 + 3 + 129]
q = bit_form[0x29a + 3:0x29a + 3 + 129]
d_mod_pm1 = bit_form[0x31e + 3:0x31e + 3 + 0x80]
d_mod_qm1 = bit_form[0x3a1 + 3:0x3a1 + 3 + 0x80]
inv_q_mod_p = bit_form[0x424 + 3:0x424 + 3 + 0x81]

print(f'--- n ---\n{"".join(n)}\n')
print(f'--- e ---\n{"".join(e)}\n')
print(f'--- d ---\n{"".join(d)}\n')
print(f'--- p ---\n{"".join(p)}\n')
print(f'--- q ---\n{"".join(q)}\n')
print(f'--- d_mod_pm1 ---\n{"".join(d_mod_pm1)}\n')
print(f'--- d_mod_qm1 ---\n{"".join(d_mod_qm1)}\n')
print(f'--- inv_q_mod_p ---\n{"".join(inv_q_mod_p)}\n')

--- n ---
0000000010011111111011110001000110001111010111010101110011011000100100111010000011001001111111101010110011010100011110001010001011000010110111100111100111011110000111000011110111111010100000011001110001110111010100010000011010100011110000011111100110110100100100111000010010001001010010011100111100110110001011000101101000100000011000110000101011010100111011101100001001010011101111111000100000010001111011100011011100111100100101110000011000111100111110010000001010110110001011011010010011001111100110101000000001011100000011001001011101011100000100110000000010010100011100010111100011101010110010100110011001000001101001000000010110100101010101000101000101010100110001100100001111010111001000100010011110000111010001000001011100010010001110000000000100000100010101100100101001101000011111011101010100101110000111110100010110100100001000101001100010100101111110101010001010001111111000111010010110100110000110100001001000011110010101111101110011101110010111011001011001111101110010110111100011010001001100001100010110000011010111011101011001110110100101010100000100000110110001111000001000010010011001101001100011111101101111111010010011000111000001110101111101010101111011101100001111001110110111110010010001110111011000000001001000111110111000110101101100111010101000101010111110111111110010001010001101001110000010001010101010100110110001011111100110111010001010011110001110111110101111111111011111111110110010101100100000110110011011110001011111000110100100000000110110101000111011111101111001001001011100111111110010010000111011100001101001101100111000100110110111001001111110000011011001101101011010111100111011110101000010111101000001000101101001010000100010001110011101100010001010100000000010010011001010001010101001110010110110110101101111001100011000100001111010010000001001111110010010110110010100000011111001000110011100100100101100101111010111110110110100010000011011100011011110000110111001101100111001100100000011000010101000011000001111000110111101011101111100101000010000101011000111110100010011011001100011000111100000001101101011111111

--- e ---
000000010000000000??????

--- d ---
????????????????111100010010????????????001110100110111111??????????????????110001001101110111011100????????????110100??????111111000110??????001110001110??????011010010000010110010000000001????????????000100000010000010100010????????????001010000011??????110000????????????110110100110000101011100????????????101001010011001100??????101011??????101011010111????????????010111111110010111000101010110????????????010001101101110000??????101000??????011101??????????????????011001010000??????110010101001??????100110011100110011000110??????101010110110??????110100001110??????????????????110101101000110111??????001001101101??????111100??????111110110100110100101100??????010010011000111110????????????001100000110????????????111011011101????????????111011100100????????????101000??????????????????????????????011100100010??????001010??????????????????????????????110000001010????????????011000????????????100000101010010101????????????????????????111101????????????????????????011000000000??????000111100001111001010011????????????????????????001000000010001111111110??????110111000111010011010100??????100101??????????????????100110110100110010??????111010????????????110110??????????????????011011110110110001????????????????????????????????????111110111011????????????010011????????????????????????????????????????????????100111??????111011????????????????????????011011??????001111????????????100010001011??????111111??????????????????101101101010??????????????????111001100011001011101110110010????????????100101010111??????011101??????011001000100001110??????111011??????????????????100101011101??????????????????100000??????101011??????101011001010????????????001000011000000000??????????????????110100??????????????????110011011000000010001000011001101101110110010010??????????????????011100001111????????????010110????????????????????????011111??????????????????100101111001??????110111011100111110????????????010100100100001001101011111000000100??????010000000111????????????001111100010100010000011010110001011000001??????????????????011111111001

--- p ---
000000??????????????????????????????????????????????????????????????????101110??????????????????110111??????001010??????????????????????????????????????????001000??????????????????010010??????????????????????????????????????????????????????001001??????101001??????110111??????001101??????010110??????????????????????????????????????????101011??????????????????????????????????????????111100??????????????????101000??????????????????100110??????????????????????????????111100??????101100??????????????????110101??????111000??????100101??????010011??????110111??????100011??????110010??????111010??????000101??????011100??????100000??????110111??????000000??????111100??????010010??????110101??????010111??????101000??????000011??????000010??????111110??????111011??????000101??????010101??????010100??????110101??????011111??????001010??????011010??????000101??????111011??????010010??????011011??????010101??????111111??????101111??????111001??????110101??????010101??????000000??????111001??????000110??????110010??????010111??????

--- q ---
??????001011??????100010??????110110??????000010??????101101??????010110??????101100??????011001??????100001??????001011??????101101??????110111??????101011??????011101??????001100??????101100??????010100??????000100??????001011??????001111??????100111??????110110??????010100??????000110??????001100??????100000??????000011??????101110??????000100??????101100??????011010??????100001??????001010??????100110??????111101??????111111??????100111??????101000??????001001??????111100??????011110??????111101??????111101??????100100??????001101??????110110??????100101??????010011??????111100??????100100??????011011??????011110??????100011??????100111??????010000??????101110??????110011??????110011??????011110??????000000??????010010??????111010??????110100??????110000??????111001??????110100??????000001??????010101??????100010??????101100??????010001??????010110??????111010??????011000??????111010??????101110??????100101??????101100??????000110??????011100??????010000??????110110??????010000??????110000??????010100??????100101

--- d_mod_pm1 ---
????????????010101??????011111??????????????????100100010101011000011111100101??????????????????010110110010011000??????110111001001??????110110011111000101??????100001111111??????????????????010100101010011111101001011110001110??????????????????101000??????100100??????111101100100000101????????????011010111100001011??????010101??????110000????????????????????????????????????001001????????????111101??????100010001111????????????????????????000011??????????????????001001010010110001????????????100000??????001000010100000010110100????????????101101111011??????????????????001000????????????011100????????????????????????????????????011110100001111111001101101000??????????????????????????????110010111100??????????????????110100??????000100111110????????????110101??????001001000010??????001110100011????????????000111000101110010????????????110110010011??????110101100111010101??????000111000111??????111110??????????????????111110????????????101100??????001011??????101000????????????001010??????110011011100??????????

--- d_mod_qm1 ---
01100001000001110110000000??????????????????????????????000100????????????011011??????????????????011110??????011111????????????001010101011101110011010011001????????????101110??????101101101001??????010011101010??????011100101101??????????????????????????????100010010000110101101010010010????????????100001????????????100110??????010010??????111111????????????????????????000101000011101110110111100010??????101001??????????????????010010????????????010000??????101000????????????110100101100??????011110110100??????100111??????000111101111????????????000010??????000010100111001100??????111111000011110000100110111101??????????????????????????????101110000010??????001010101101100110????????????????????????000011??????011110????????????????????????100001111011??????000000????????????010101????????????001110????????????111001111111010111101100011000????????????011000??????000000??????????????????????????????????????????101010??????110010??????100000100100??????001111011011101010??????????????????????????????00110001

--- inv_q_mod_p ---
0000????????????010010010000??????????????????????????????000100010001100011001011101001??????001101????????????000000????????????001111??????010010101000??????010011001111000100????????????010110010110000110??????????????????100101001010??????010000????????????????????????101000??????011010110011101101100111010100010011??????011110001010011110111000111110100001110100??????010101100100101110000001??????011011??????101111??????111011100000011110??????100111001010110101????????????001001110010111011??????110010????????????111101????????????????????????????????????000001001111????????????100000000110??????100100001010001010??????110010??????011001??????????????????110010000100010010111000100010??????????????????010100100001011100??????101001????????????????????????011100111000100101100111??????100110??????101011??????????????????001111????????????000010??????111100??????010111??????011101????????????010011001111????????????100100????????????000001??????011101110000100011001101111011????????????101110100010??????001010??

$p, q$ の下位 534 ビット (1032 ビット中) が交互に ? になっている
$p = p_0 + p_1 \cdot N + p_2 \cdot N^2 + p_3 \cdot N^3 + \cdots + p_{171} \cdot N^{171}$ ($p_i$ は 6 ビット，$N = 2^6$) とすると，
$p \cdot q = p_0 q_0 + (p_1 q_0 + p_0 q_1) N + (p_2 q_0 + p_1 q_1 + p_0 q_2) N^2 + \cdots + (p_{171} q_0 + \cdots + p_0 q_{171}) N^{171} + (p_{171} q_1 + p_{170} q_2 + \cdots + p_1 q_{171}) N^{172} + \cdots$
と表せる
交互に ? になっている部分は一意に定まる
下位 532 ビットがわかったので Coppersmith's attack にかけてみるが，上位ビットが得られない
(適当な p, q を生成して試してみると少しだけビット数が足りないっぽい)

続く 6 ビットを総当り (64 通り) で調べる

Sage で解く

from string import printable
from Crypto.PublicKey.RSA import *

pem = '''
MIIEpAIBAAKCAQEAn+8Rj11c2JOgyf6s1Hiiwt553hw9+oGcd1EGo8H5tJOEiUnP
NixaIGMK1O7CU7+IEe43PJcGPPkCti2kz5qAXAyXXBMAlHF46spmQaQFpVRRVMZD
1yInh0QXEjgBBFZKaH3VLh9FpCKYpfqij+OlphoSHlfc7l2Wfct40TDFg13WdpVB
BseCEmaY/b+kxwdfVe7Dzt8kd2ASPuNbOqKvv8ijTgiqpsX5uinjvr/3/srINm8X
xpANqO/eSXP8kO4abOJtyfg2bWvO9QvQRaUIjnYioAkyiqcttbzGIekCfktlA+Rn
JLL19tEG43hubOZAwqGDxvXfKEKx9E2Yx4Da/wIDAQA?AoI?????8S??Om/???xN
3c??0?/G?OO?aQWQB??ECCi??KD?w??2mFc??pTM?r?rX??X+XFW??Rtw?o?d???
ZQ?yp?mczG?q2?0O???1o3?Jt?8?+00s?SY+??MG??7d??7k??o?????ci?K????
?wK??Y??gqV????9????YA?Hh5T????ICP+?3HTU?l???m0y?6??2???b2x?????
?+7??T????????n?7????b?P??iL?/???tq???5jLuy??lX?d?ZEO?7???ld???g
?r?rK??IYA???0???zYCIZt2S???cP??W????f???l5?3c+??UkJr4E?QH??PiiD
WLB???f5A?G?A???????????u???3?K???????I???S?????????J?p?3?N?W???
????r???????8???o???m?????8?s???1?4?l?T?3?j?y?6?F?c?g?3?A?8?S?1?
X?o?D?C?+?7?F?V?U?1?f?K?a?F?7?S?b?V?/?v?5?1?V?A?5?G?y?X?AoGB?L?i
?2?C?t?W?s?Z?h?L?t?3?r?d?M?s?U?E?L?P?n?2?U?G?M?g?D?u?E?s?a?h?K?m
?9?/?n?o?J?8?e?9?9?k?N?2?l?T?8?k?b?e?j?n?Q?u?z?z?e?A?S?6?0?w?5?0
?B?V?i?s?R?W?6?Y?6?u?l?s?G?c?Q?2?Q?w?U?l??GA??V?f???kVYfl???WyY?
3J?2fF?h/???UqfpeO???o?k?9kF??a8L?V?w??????J??9?iP????D???JSx??g
?IUC0??t7???I??c??????eh/No?????y8???0?E+??1?JC?Oj??HFy??2T?1nV?
HH?+???+??s?L?o??K?zc?????BhB2A?????E??b???e?f??KruaZ??u?tp?Tq?c
t?????iQ1qS??h??m?S?/????FDu3i?p???S??Q?o??0s?e0?n?Hv??C?CnM?/Dw
m9?????uC?Ktm????D?e????h7?A??V??O??5/XsY??Y?A???????q?y?gk?Pbq?
????MQK?gQ??SQ?????ERjLp?N??A??P?So?TPE??WWG???lK?Q????o?aztnUT?
eKe4+h0?VkuB?b?v?7ge?nK1??Jy7?y??9??????BP??gG?kKK?y?Z???yES4i??
?Uhc?p????c4ln?m?r???P??C?8?X?d??TP??k??B?dwjN7??ui?K????????
'''

def main():
    global pem
    pem = pem.replace('\n','')

    b64_enc = printable[10+26:10+52] + printable[10:10+26] + printable[:10] + '+/'
    b64_dec = dict()
    for i in range(64):
        b64_dec[b64_enc[i]] = i

    bits = ''
    for p in pem:
        if p == '?':
            bits += '?'*6
        else:
            bits += format(b64_dec[p], '06b')

    hex_form = []
    bit_form = []

    cnt = 0
    f1 = ''
    f2 = ''
    for i in range(0, len(bits)-8, 8):
        byte = bits[i:i+8]
        u = '?' if '?' in byte[:4] else hex(int(byte[:4], 2))[2:]
        l = '?' if '?' in byte[4:] else hex(int(byte[4:], 2))[2:]
        f1 += f'{byte} '
        f2 += f'{u}{l} '
        if cnt % 4 == 3:
            print('{:3x}'.format(cnt-3), ':', f1, ':', f2)
            f1 = ''
            f2 = ''
        cnt += 1
        hex_form.append(f'{u}{l}')
        bit_form.append(byte)

    n = bit_form[0x7 + 4:0x7 + 4 + 0x101]
    e = bit_form[0x10c + 2:0x10c + 2 + 3]
    d = bit_form[0x111 + 4:0x111 + 4 + 257]
    p = bit_form[0x216 + 3:0x216 + 3 + 129]
    q = bit_form[0x29a + 3:0x29a + 3 + 129]
    d_mod_pm1 = bit_form[0x31e + 3:0x31e + 3 + 0x80]
    d_mod_qm1 = bit_form[0x3a1 + 3:0x3a1 + 3 + 0x80]
    inv_q_mod_p = bit_form[0x424 + 3:0x424 + 3 + 0x81]

    print()
    print(f'--- n ---\n{"".join(n)}\n')
    print(f'--- e ---\n{"".join(e)}\n')
    print(f'--- d ---\n{"".join(d)}\n')
    print(f'--- p ---\n{"".join(p)}\n')
    print(f'--- q ---\n{"".join(q)}\n')
    print(f'--- d_mod_pm1 ---\n{"".join(d_mod_pm1)}\n')
    print(f'--- d_mod_qm1 ---\n{"".join(d_mod_qm1)}\n')
    print(f'--- inv_q_mod_p ---\n{"".join(inv_q_mod_p)}\n')

    n = int(''.join(n), 2)
    rev_p = form8to6(p)[::-1]
    rev_q = form8to6(q)[::-1]
    low_p = 0
    low_q = 0
    N = 2**6
    candidate = []
    for i in range(172):
        if rev_p[i] == rev_q[i] == '??????':
            for pi in range(N):
                for qi in range(N):
                    if ((low_p + pi * (N**i)) * (low_q + qi * (N**i))) % (N**(i + 1)) == n % (N**(i + 1)):
                        candidate.append((low_p + pi * (N**i), low_q + qi *(N**i)))
        elif rev_p[i] == '??????':
            for pi in range(N):
                if ((low_p + pi * (N**i)) * (low_q + int(rev_q[i], 2) * (N**i))) % (N**(i + 1)) == n % (N**(i + 1)):
                    rev_p[i] = '{:06b}'.format(pi)
                    break
        elif rev_q[i] == '??????':
            for qi in range(N):
                if ((low_p + int(rev_p[i], 2) * (N**i)) * (low_q + qi * (N**i))) % (N**(i + 1)) == n % (N**(i + 1)):
                    rev_q[i] = '{:06b}'.format(qi)
                    break
        if len(candidate) > 0:
            break
        low_p += int(rev_p[i], 2) * (N**i)
        low_q += int(rev_q[i], 2) * (N**i)
        assert (low_p * low_q) % (N**(i + 1)) == (n) % (N**(i + 1))
        print(f'{i} : {rev_p[i]} {rev_q[i]}')
    
    # print(f'--- low p ---\n{low_p}\n')
    # print(f'--- low q ---\n{low_q}\n')

    # print()
    # print('n :', ''.join(n))
    # print()
    # print('pq :', bin(low_p * low_q))

    for cand in candidate:
        for low in cand:
            M = low.bit_length()

            PR.<x> = PolynomialRing(Zmod(n))

            f = x * 2^M + low
            f = f.monic()

            diff = f.small_roots(X=2^(1024 - M), beta=0.48, epsilon=0.02)
            if len(diff):
                full = diff[0] * 2^M + low
                if low == cand[0]:
                    p = int(full)
                    q = n // p
                    assert n == p * q
                else:
                    q = int(full)
                    p = n // q
                    assert n == p * q
                print()
                print('p =', p)
                print('q =', q)
                e = 65537
                d = pow(e, -1, (p-1)*(q-1))
                key = construct((int(n), int(e), int(d)))
                data = key.exportKey()
                open('ans.pem', 'wb').write(data)
                exit()

def form8to6(v):
    s = ''.join(v)
    offset = len(s) % 6
    if offset == 0:
        return [s[offset + i:offset + i + 6] for i in range(0, len(s), 6)]
    else:
        return [s[:offset]] + [s[offset + i:offset + i + 6] for i in range(0, len(s) - 6, 6)]

if __name__ == '__main__':
    main()

ssh godam@corrupted.chal.ctf.acsc.asia -i ans.pem

SusCipher

z3 を使って解く
鍵をハッシュして subkeys を得ているが，そこは無視して各 subkey に対して z3 の変数を持たせる
送信する平文に関してはすべてのビットに対して，そのビットのみを 1 にしたものを送る

from pwn import *
from z3 import *
from SusCipher.task import SusCipher
S = SusCipher.S
P = SusCipher.P

ROUND = 3
BLOCK_NUM = 8
MASK = (1 << (6 * BLOCK_NUM)) - 1

def main():
    io = remote('suscipher.chal.ctf.acsc.asia', 13579)

    plains = [1 << i for i in range(48)]
    io.sendlineafter(b'> ', ', '.join(map(str, plains)).encode())
    encs = [int(v.strip()) for v in io.recvline().decode().split(",")]
    
    solver = Solver()
    sbox = z3.Function('SBOX', z3.BitVecSort(6), z3.BitVecSort(6))
    for i in range(1 << 6):
        solver.add(sbox(i) == S[i])
    subkeys = [[BitVec(f'key_{i}_{j}', 6) for j in range(8)] for i in range(1 + ROUND)]
    for p, e in zip(plains, encs):
        ze = z3_enc(p, subkeys, sbox)
        for a, b in zip(ze, divede(e)):
            solver.add(a == b)
    
    if solver.check() == sat:
        model = solver.model()
        key = [model[subkeys[0][j]].as_long() for j in range(8)]
        key = combine(key)
        print('key :', key)
        io.sendlineafter(b'> ', str(key).encode())
        print(io.recvline().decode())
    else:
        print('UNSAT')

def z3_enc(inp, subkeys, sbox):
    block = divede(inp)
    block = xor(block, subkeys[0])
    for r in range(ROUND):
        block = sub(block, sbox)
        block = perm(block)
        block = xor(block, subkeys[r + 1])
    return block

def divede(inp):
    l = []
    for _ in range(BLOCK_NUM):
        l.append(inp & 0b111111)
        inp >>= 6
    return l[::-1]

def combine(block):
    res = 0
    for v in block:
        res <<= 6
        res |= v
    return res

def xor(a, b):
    return [x ^ y for x, y in zip(a, b)]

def sub(block, sbox):
    return [sbox(v) for v in block]

def perm(block):
    bits = []
    for b in block:
        for i in range(6):
            bits.append(Extract(5 - i, 5 - i, b))
    buf = [0 for _ in range(6 * BLOCK_NUM)]
    for i in range(6 * BLOCK_NUM):
        buf[P[i]] = bits[i]
    return [Concat(buf[i : i + 6]) for i in range(0, 6 * BLOCK_NUM, 6)]

if __name__ == '__main__':
    main()

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

ACSC 2023 (Crypto) Writeup

目次

Merkle Hellman

Check_number_63

Dual Signature Algorithm

Corrupted

SusCipher