ACSC 2023 (Crypto) Writeup

## 目次
1. [Merkle Hellman](#merkle-hellman)
2. [Check_number_63](#check_number_63)
3. [Dual Signature Algorithm](#dual-signature-algorithm)
4. [Corrupted](#corrupted)
5. [SusCipher](#suscipher)

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

```py
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 を使う)

```py
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 で解けそう  
    ```math
    (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 で解く
    ```py
    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](https://www.rfc-editor.org/rfc/rfc2313#:~:text=7.2%20Private%2Dkey%20syntax))
    ```
    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
    ```
* 
    <details><summary>16進数に変換する</summary><div>

    ```py
    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 : ???????? ???????? ???????? ????????  : ?? ?? ?? ??
    ```
    </div></details>

    * 最初は "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 の長さと一致する)
* 各パラメータを見てみる
    ```py
    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 で解く
    ```py
    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 にしたものを送る
```py
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()
```