# seccon2022

[toc]

### crypto/pqpq

#### 参考にしたwriteup

* 作問者(kurenaif)
- https://youtu.be/b5IX6MM6LIk?t=9m0s
> pqpqの解説は09:00から19:47まで
* 最後の詰め
- https://liniku.hatenablog.com/entry/2022/11/17/085258
> 平方根の求め方についての実装

#### 考えたことの時系列

* 16:00 RSA暗号の基本をまなぶ
- https://www.youtube.com/watch?v=HKDyUELFdXs

* 18:00 CTFの解き方のセオリーを過去問でさぐる
- https://furutsuki.hatenablog.com/entry/2021/03/16/095021
- 「pやqに関連する値を暗号化している」
- https://furutsuki.hatenablog.com/entry/2020/12/27/160652#Crypto-rsa
- 「nが多くの素因数に分解される」→ Multi-prime RSA
- https://furutsuki.hatenablog.com/entry/2021/03/15/174550

* 20:00 Nを構成する素因数が1つが求まった

# c1-c2 mod n == 2p^e mod n
vp = (c1 - c2) % n
p = math.gcd(vp, n)

* 26:00 すいみん　( ˘ω˘)ｽﾔｧ

* 翌8:00 Nを構成する素因数がすべて求まった

# eが偶数であることに気が付く
# c1+c2 mod n == 2q^e mod n
vq = (c1 + c2) % n
q = math.gcd(vq, n)
r = n // p // q

* 12:00 試行錯誤... eが偶数なので、dが求まらない...
- modのうえで、平方根をもとめればよさそう
- p, q, rは互いに素なので、平方根を独立して求めて、かけ合わせればよいはず

    # m2p = m2 % p
    # m2q = m2 % q
    # m2r = m2 % r

- 平方根をとる方法は、「Tonelli-Shanks Algorithm」が使えるらしい。適当なPython実装を拾う
- https://tjkendev.github.io/procon-library/python/math/tonelli-shanks.html
- ⇒ たまにエラーになる... 初期乱数次第で結果が気まぐれ
- https://tex2e.github.io/blog/crypto/tonelli-shanks-algorithm
- ⇒ 平方根の解が2つ出てくる...
- ⇒ mの復号結果は2 * 2 * 2 = 8通りなので、全部デコードを試してみる

* 翌14:00 タイムアップ...

#### 手元のコード

:::spoiler solve.py

import math
import libnum
from Crypto.Util.number import *


def legendre_symbol(n, p):
    ls = pow(n, (p - 1) // 2, p)
    if ls == 1:
        return 1
    elif ls == p - 1:
        return -1
    else:
        # in case ls == 0
        raise Exception('n:{} = 0 mod p:{}'.format(n, p))

def check_sqrt(x, n, p):
    assert(pow(x, 2, p) == n % p)

def modular_sqrt(n:int, p:int) -> list:
    if type(n) != int or type(p) != int:
        raise TypeError('n and p must be integers')

    if p < 3:
        raise Exception('p must be equal to or more than 3')

    if not isPrime(p):
        raise Exception('p must be a prime number. {} is a composite number'.format(p))

    if legendre_symbol(n, p) == -1:
        raise Exception('n={} is Quadratic Nonresidue modulo p={}'.format(n, p))

    if p % 4 == 3:
        x = pow(n, (p + 1) // 4, p)
        check_sqrt(x, n, p)
        return [x, p - x]

    # Tonelli-Shanks
    q, s = p - 1, 0
    while q % 2 == 0:
        q //= 2
        s += 1
    z = 2
    while legendre_symbol(z, p) != -1:
        z += 1
    m, c, t, r = s, pow(z, q, p), pow(n, q, p), pow(n, (q + 1) // 2, p)
    while t != 1:
        pow_t = pow(t, 2, p)
        for j in range(1, m):
            if pow_t == 1:
                m_update = j
                break
            pow_t = pow(pow_t, 2, p)
        b = pow(c, int(pow(2, m - m_update - 1)), p)
        m, c, t, r = m_update, pow(b, 2, p), t * pow(b, 2, p) % p, r * b % p
    check_sqrt(r, n, p)
    return [r, p - r]


with open("output.txt") as f:
    lines = f.readlines()
    e = eval(lines[0].split()[-1])
    n = eval(lines[1].split()[-1])
    c1 = eval(lines[2].split()[-1])
    c2 = eval(lines[3].split()[-1])
    cm = eval(lines[4].split()[-1])

print(f"e = {e}")
print(f"n = {n}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")
print(f"cm = {cm}")

print("----")

# c2 = (p-q)^eを二項定理で展開
# eが偶数なので、(-q^e)=(-1)^偶数(q^e)=q^eとなるので、
# c2 = p^e + q^e mod n

# c1-c2 mod n == 2p^e mod n
vp = (c1 - c2) % n
p = math.gcd(vp, n)

# c1+c2 mod n == 2q^e mod n
vq = (c1 + c2) % n
q = math.gcd(vq, n)
r = n // p // q

print(f"p = {p}")
print(f"p is factor of n ? {n % p == 0}")
print(f"q = {q}")
print(f"q is factor of n ? {n % q == 0}")
print(f"r = {r}")
print(f"r is factor of n ? {n % r == 0}")

assert p * q * r == n

print("----")

phi = (p-1) * (q-1) * (r-1)
print(f"phi = {phi}")

## e = 2 * 65537 が合成数なので、phiと互いに素になってないので、NG
#d = pow(e, -1, phi)

#while phi % 2 == 0:
#  print("not relatively prime!! ", phi)
#  phi //= 2

#while phi % 65537 == 0:
#  print("not relatively prime 65537 !! ", phi)
#  phi //= 65537


cmp = cm % p
cmq = cm % q
cmr = cm % r
print(f"cmp = {cmp}")
print(f"cmq = {cmq}")
print(f"cmr = {cmr}")

print("check cm", (cmp * cmq * cmr) % n == cm)

## cm = (m^65537)^2 mod n である
## 2乗したときに、上記の値に合致するようなcm' = m^65537 mod n の値が知りたい
## cm' = (mp mod p) * (mq mod q) * (mr mod r) mod n となる
## Tonelli-Shanks で n = p * q * rに分割して、各々の平方根をもとめて、条件に合うものを列挙する

mp_list = modular_sqrt(cmp, p)
print("mp list", mp_list)
mq_list = modular_sqrt(cmq, q)
print("mq list", mq_list)
mr_list = modular_sqrt(cmr, r)
print("mr list", mr_list)

'''
mp 3505255395972154267761448617694891007211859720395890992569146044751635155301253956186252320583556066707432335903844117501984423930218920343822505357680714
mq 2808415004342417472535489784285151726899488035581377746910855619764896925616370131254826941432074654629302410762459898065332716624587315421328482625709708
mr 8993377129707051777777793399478948321486507452204039611715827587140163465984628186155142174366509016594688211791837041273560359376046094901187385370307654
'''

for mp in mp_list:
    for mq in mq_list:
        for mr in mr_list:
            m_dash = (mp * mq * mr) % n
            
            ## check ... いずれもfalse..
            print("check p", (m_dash ** 2) % p == cm % p)

            d = pow(65537, -1, phi)
            # print("d", d)

            m = pow(m_dash, d, n)
            print(long_to_bytes(m))

# -----------------------------------------------------------------------------
### (11/29) 追記

ip = pow(q * r, -1, p)
iq = pow(r * p, -1, q)
ir = pow(p * q, -1, r)
kp = ip * q * r
kq = iq * r * p
kr = ir * p * q

for mp in mp_list:
    for mq in mq_list:
        for mr in mr_list:
            ## 中国剰余定理の理解が不十分...
            m_dash = (kp * mp + kq * mq + kr * mr) % n
            d = pow(65537, -1, phi)
            m = pow(m_dash, d, n)
            print(long_to_bytes(m))

:::

:::spoiler 出力

$ python3 solver.py
e = 131074
n = 587926815910957928506680558951380405698765957736660571041732511939308424899531125274073420353104933723578377320050609109973567093301465914201779673281463229043539776071848986139657349676692718889679333084650490543298408820393827884588301690661795023628407437321580294262453190086595632660415087049509707898690300735866307908684649384093580089579066927072306239235691848372795522705863097316041992762430583002647242874432616919707048872023450089003861892443175057
c1 = 92883677608593259107779614675340187389627152895287502713709168556367680044547229499881430201334665342299031232736527233576918819872441595012586353493994687554993850861284698771856524058389658082754805340430113793873484033099148690745409478343585721548477862484321261504696340989152768048722100452380071775092776100545951118812510485258151625980480449364841902275382168289834835592610827304151460005023283820809211181376463308232832041617730995269229706500778999
c2 = 46236476834113109832988500718245623668321130659753618396968458085371710919173095425312826538494027621684566936459628333712619089451210986870323342712049966508077935506288610960911880157875515961210931283604254773154117519276154872411593688579702575956948337592659599321668773003355325067112181265438366718228446448254354388848428310614023369655106639341893255469632846938342940907002778575355566044700049191772800859575284398246115317686284789740336401764665472
cm = 357982930129036534232652210898740711702843117900101310390536835935714799577440705618646343456679847613022604725158389766496649223820165598357113877892553200702943562674928769780834623569501835458020870291541041964954580145140283927441757571859062193670500697241155641475887438532923910772758985332976303801843564388289302751743334888885607686066607804176327367188812325636165858751339661015759861175537925741744142766298156196248822715533235458083173713289585866
----
p = 8609258896430210586523688955272794335561428099377427081622836355194006054569349679983850344916908011330202034512905353365631416251631307084038768336538857
p is factor of n ? True
q = 7572427786695057270624844967644562609112132599800420296747189080920032359205995588384031542287784540006438555802994008688795974493684400576592403320929717
q is factor of n ? True
r = 9018251874561850467651399512661829039310834429345808807288228370045576292997274498659156953954383290793552486677903139680704353709352146165598701061994853
r is factor of n ? True
----
phi = 587926815910957928506680558951380405698765957736660571041732511939308424899531125274073420353104933723578377320050609109973567093301465914201779673281463017920022222225118880476785013994594762972240080110785103801005723173327944717011397200915239153708586410443288034659171386345983812732533578398339068074287103302221349117297844601479450633827001807630965495422738345381660807649937337946238685560749011749864111212055524121033345631736184813253469513428875392
cmp = 2287179356847297183312542129524995447553817328047448757096131460179825798241973797644063711871566679239431277892005404343017794969820317535671143216719836
cmq = 4732264978189530429121080608212629555796104108065105246241158291364647817225411351463093168220813792049256763152646128312376175757774405436789308746191500
cmr = 3182671426873054929595306276860360481660223644851298782799315521406119797304753297574880116993651331245681619697787829754323539755177857260554640173408793
check cm False
mp list [5104003500458056318762240337577903328349568378981536089053690310442370899268095723797598024333351944622769698609061235863646992321412386740216262978858143, 3505255395972154267761448617694891007211859720395890992569146044751635155301253956186252320583556066707432335903844117501984423930218920343822505357680714]
mq list [4764012782352639798089355183359410882212644564219042549836333461155135433589625457129204600855709885377136145040534110623463257869097085155263920695220009, 2808415004342417472535489784285151726899488035581377746910855619764896925616370131254826941432074654629302410762459898065332716624587315421328482625709708]
mr list [8993377129707051777777793399478948321486507452204039611715827587140163465984628186155142174366509016594688211791837041273560359376046094901187385370307654, 24874744854798689873606113182880717824326977141769195572400782905412827012646312504014779587874274198864274886066098407143994333306051264411315691687199]
check p False
b'\n\x9fOt\x00\xbf.\xa2\xfeqy\x1d\xd4}\x8a|7\xed\x04$\xe1\xb7\x9c\x93|c\x07\xb3]\xceO\xdb\t"^\x7f\x7fJZ."vCp\x98#N\xab\xdd\x1fd\xbcX\xb2\xbcih\'R\xb1\xf6\xa1\x90*oF\xad\x97zQU\x00\xdeq\xd6#X\xe4c\xe1I3\x99\x91\xe6\xd51\xa9:\xc3\x16\xd2\xd0\x1e\x0f\xff\x05vW\xbe\xb4u \xff\x9c\x1a\xf4\xf4\xdb\x08p\xcc\x05E\x86\x0e\xae\xa0\xd8>d\xf5\xb8\xa8\xac\xcd\xd0V\xc7\xf9y\x9a\xebD\xf8\xea"d\xd7I\xd6\xef\xe0\xeaE\xeb\xb1\xf7\xc5\x8883\xeb\xed\xfcC}H\xaf\xbd\x17\xa9\xf3\x10\xf5\xc7\xd5F\x85N\xf9\xe4\xc0z\xd3m\x16\xb8&\x13E\xaf\xca\xf7\xbaa\x87^e\xc5jo'
check p False
b'5\x8c\xb8\xe4\x13\xb7\r\x01\xc2^\xa1o\\\x1f\xf2i\x9cF!\x84\xf5\xa91.\xbbQT\x8f\xc9\x03w\x0b2\xe7\n\x1bn\x06\x91a\xd5V\xd9\x913\xabL\x91\x19\xa8r\xacJpuK\xc3\xbf>\xbf\xac\x84\xed\x1em\x87\xa4\x066\x91E\xe5\xeas\x0f\xb51b\xa9f\xe61I\xcfN\xba\xba\x03\t\x1cqD\xd75\xf59\x04\xeb\xf1<\xec\x8b%\x8a\x808\x8e\x0b\t\xb4\xa2\xb3I7\xea\x83\xfa\t\x9dU\x15q\x17\xb5\xe5s\xe4\xedj>J\xb4\xbdr\x02z\xf7\xe8=\x06&$\xd6u\x8d\xcf\xe2\x94\x15\x8a\xad\x19+\x93\xd0\xfa\x95g\xc7>\xe61\x1f\x13\xce-K\xc9\xbeS\xce\x99\x8d\xf1\xbeKE)\xf4\xf3\xad\x83\xf5\x7fP\xf2Q\x00U\x84\xbe\xc3'
check p False
b'13:\x8d\xf9\xcf\xbf\x00\x19\x19=\xd9&n\xf9^)\xe1lrN\x95n\xb4\x05?\x7f\xfa\x80\x9a0\xa1\x002\xa2g\xedE\xa5\x1a\x04\xee^\xc7\xcf\xff\xb1\n\xfb\xbew\xc6\x80\xd3\x8f\xf5s|b\x86\x06\xe5\x86\x9c<{\xd5\x1c\x93\xb0\x98\xfd\xa6[Q}\xbf\xe2\xfcpe\xcf\xb1r\n-\xde\xd5D8f\xa2\x15.\x8a\xfc\x8d\xd5{\xa6&\x04wT\xa4\\\xe1\xe6\xd8\xa0k\xab\xe6\x02\x946\x0c\x95tn\x0e\xc0 Y\x9a\xd8\xa0\xdef\x97\xbfsn^w\x9f\xf6\x8a\x9c\xff\xd3E@#\xbb\xc9#\xf1^\xba\xa36N\xa3\xe0Ks\x1d\xba\r\x02O\x92\xb8E\x84\x156\x9d\x0e\xc5w\xd6\x16\xb2\xbd\x0c\xb2\x15\xd1\x82vX\xdc`\xe3$m0\xdd\xc1\xea'
check p False
b"\x01\xc8|&\x96-\x90\xe0w\x98\xe6U\x7f\xb8#l\xac\x9a\x04\xe8\xac\x94\xb0D.\x04\x99bl1G\x99\xafm\x8as+\x81\x04\xe6T\xdb\xe7\taTB\xb8\x95\xb6\xd8AJ\xbc\xc0\x8f\x07\xe6kAIf\xc9\xc5@m`\x15\r`\xcb\xcaO6\xae\xa7\xd3\xc2\xb4\xad\xb17\xe0}A\xeaS\x0f\xbc\xb9\xfe,\xce\xff\xe7\xa79\\S:\x8d\x18\xb7\xe9]\x97\x0b\xaa\xebQ\xb0N\x9e^+\xb3\x0b\xaelA~\xeaR\xcdq\x8c4'\x03.\xbf\x97\xa7\x038\xcc\xa2W8y\xcaGOb{\xc8\x1d\x90\xa1`\x9c\x962-\xe9d\xec\xb5\xee8\xdf\x12+\x92\xad\x83\xedXA\xb9\xc63\x8a\xef\x15\x01\xeb$^=\x18\x91\x88C\x18\xbc*\xe9\xc4\xdd\xce\xc0"
check p False
b'\x15\xfb\t\x0fi`s\x128\xac\xe1@\xd4\xa2\xfe\xef\x85\x1eg\xce\xf7M\xc2\x9c\rzY\r\\N\xf9O\x1f\x08[\x16\xbdc\x84\x90\xfb\x91\\b$\x13!\x90\xfe\xffR\x15Cs\x9a\x8b\xa1c\xb2\x92\x13F\x8f\xc9\xdf\x85\xb3L?\x9eL<\xb1\xc9$\xe6\xc4\x08)7\x8c\xc9\xfc\xd47\xadU^w\xc7\xf6S\xfa\xb6\xe6K\xdb\x1a\xc9u]w+l\xa4\x13\x91\x8c\xfd\xda\xd1\x87\x8d\xfb\xa1\t\xc0\xa9p\xc5\x01\xf2\n\xf3\xbc\xb3c\xd6\xff\x90\xd2\r\xa5QA>Z#\x87\xa6\xa6\xee\x9e{\xcf\xf1\xaa\xf2]\x94\x0b\xd0\xc0\x9a\xce\xdd\xd7-e/\xc5\xbe\xbd\x9e\x0b\x0fG~\xa85+\xfa\xd8\xf2\x06\xbf~k\xf7\x83\xee\xc2\xa5a7\x87\x19Bc\x19\x07\xcb'
check p False
b'\x14\xcc\x13\xe4_r0\xbd)\x81{\xd1t\xaa\x01\xd2\x95eL"\x1e\x98\xd5\xc0\xd9 /\xe1~\xc0y\xd8\xf8\xd8f\xc5\x85\xd1\x18\tB\xab\xd0\x14\x7f>\xca\x0f<v=v\xb6\x14"\xcaz\x85\xd7\x1b\x00<\x97i\x97Sr\x85\xd8\x14g\xd3\x8ca\xc6\xbb8\xa2t\xca\xeb\xf2\xad\x99\xe9\xacRr\xd4\x948\xfb\xf1\xa9O8Ob,\xb3U\x83\x92\xda\xf9Z_3_\x9d\x90\x05\x97\xfeq\x9e\xdd\xab\xc5\xb8\x11\x80\xb4\x9c\x95`^\x06vp\x01\xc4\x05\xb9\xc01\x1cQbP\xe3\x95\x07\x81\x88F[\xa3[\x8c\x0b\xff0;9\xd4c\xbcjm\x96t\xff?\xb9*\xc8\xc2\x87\x81S\x8a\xf6\x06$\x11\xeb\xfc\xbc/\xc1\xbam\xc2\xd5\xd6,:n\xcd\xa5\xdf'
check p False
b"\x13g\x032\xf1\xeaL\x99\xe3I\x0bgA\xa6\xc7[&\x1a\xc6\x19\x13\t:\xd4\xb3\xda\xe8[\xa6]S\xf0\x1d\x9d\xc7^\\\xf0Z\xd9\xc9\xd0o%~\xb5\x84\xec1\xc6\x08\xf6\x1a\xad\xe7*\xf8\xf1\x03\xbf\xf9U\xc8`\xb2I\xe9X\xb1\xb7\xa5z\x9eT\xae\xbd\xfd\xd6\x80N\xcd\x1eb\xe3%Uv\xf9B\xa4\xb6D/\xc1JS\x0e\xa9\xaf\xa2<\x16\xeca\x8c(\n\xc2\x0f\xb7+\xc0\x80&Z7\xf0\x14D(\x17'\xb2\xd4\x81\x8b\x9c.\x07Kw\xbd1\x9b/\x9b+\xe6~<d\xd2\xda\r\x18\x1dg\xae\x0c\xaf\xfd\x9a\xf3\xfcM\x0c\xdc\x98\xb3\x1f\xb6\xbe\xdf\xba\x17\x84\x8e\xf0\xb3Ip\xcbK\x90\xd3\xc7:\xd8w5/X\xb0\x119\x17\xa4\x93F\x9a\xdf\xc4"
check p False
b'\t\xff\x07\x8f]|\xd1p\x92\xbfK\xb2$\x87\x19 N_>\xc1\xc0\xed\xcd\x88\x85xU\x17\x91\xbd\xed\x00\xd2\x86\xbb\x90\xdawa\xf8=.%_4h\xcc\x07H\x94\x88>N\x12\x1fg\xcb\xeb\x98\xf5\xcc\x8b\xbd\x12+\xfe\x1a\x12u^\xd7w\xe3\t^\xa7\xd0\xcf\x9b\xcb>\n\xa2\x1d\\\x85\xc7\xe8\xfc\xe7h\xd0\xb4?J%(;\xe7r\xe6y;\xbfs\xff%iO_ pH\xe4;\xd7\x19M\x13\x9c\x99,\x1f\x8d\xb3P\x9ag\xb0Y7\x88\xa4.\xab\xa1\xbd\xbf\x03+R_\x9d\x05\xe9\x9d;JU\xbb\xfbM\x07\x11\xa5}\xc1\x00\xd9K\xf0oB\x945\x03\xe2.\xc3\x0f;s\x99\xc2\xd9YFP\xbc\x18\xab\xc2*\xcf\x7fJ=\x87\xa6:"i'
b'\r\xc9\x08\xfb\x1e\x15}e\xc4\xd5\x93\x11\xb1\x1b*\xb7\x00\x91\x0f\xc0\xf6\xb8\xb3Xw: v\xef\xad\x07w\xd4\xad\x1a\xb5\x8b\xcf\xdaK\x96\xc6\xf8\x1f\xda\xcd\xc6\xf3h{y\x88\xc9G\r&\xbdyB\x81y?\xbd\xb4\x08K\xd8]\xa8U\xa7\xca\xf1\xf25\x9f5r\xfd3U\xdf\xba\xcb\xa0\xe7c\xba^\xaf\x98\xe0\x0bt\x85\xf2\xb7\xfa\xc1\xf2\xd8\xc7\xa2\xd1\xe0\xf5g\x9dV{;\x90\x07\x1e\xa0\xd8\xc49\xa5\x93\x94\x85c1\xe1F\x80\xe0\xae\x95\xb8`\xb9\xe0;\xabH\nzr\xfb\xf9\xce\xc6Ek[|\x84N\x06\x13\x91\n\x0e\xc0E\x83\xbd 4\x03\x13~|2[\xa6"\x97\x07\x05\xfbSyQ\x0fUFo\xf1a\x1e&j\x8a\xaa8\xcd\xc9f\x9a'
b'\x05\x95\xd5\xb8\xd2\x8b\x8cM1j\x07)M5\x90\xdf\xbe\x0b\xa1\xda\x12\xf2\x98\xba\xa8\x9b>\xbf$/\x03I\x9c\xa2\xba\xb4\x13\x95\x95Ra\x91\xca\x0f\x15\x95\xbb`\xed\'\xe9hD\xed\xa5\xc3\xcf\x05a\xcb\xe1?\xad\x00\xf1\xa6q\x1c\x0b\xab\x7f\x8e\x13>\x8d\xab\xf1S\x07\xcaVw\xd2\'\xbfm\xb2>\x0f\x86\xf9\xf0M\xca\x16\xaf\x9c\x9b\x81A\xad\x06\xd1\xfb\xcdkZ\xf3\xa1Tt\x143\xf1$B:\x9e\xa6rO\x9c\x85xC\xc7\x01`J<\x16\xe4\xddq\xcf \x86Fi&F?\xadn\xde\xfdv{\xcf~\x14p\x1e"\x9a\xf0\n\x92\xaad\x87x\x0b\x82u\xef\xdbW\xd5\xf9\xf6\x9b<\xacuPE\xe5\xf0\xcc\xac\x1fY\x08\x123\xf9D!\xc9\\i'
b'\x08 \xf6=\xd9\xee8\xfc\x83(\x89\xcaP\x84\xed\x99\x00\xe8tI!BW\xd0\xb9\x07[(\xf8\xf8\xd9\xbb*\xf1\xe1e\xbd\xd0\x93\xf1\x88\xef\x1e\x14R\xdd\x19\xc2[\xa3\x1e;\xc4\x86\xe0\x1b\xd2\x97\x0e@\x00LDs[\xeb&\x93\x05\xce\r,\x0b\xb3A\xe8\xfb\x86\x90q\x83}\xc8!\x8c\x84\xad\xfa~\xee\x91b\x17Y\xdc\xa2\xfd\xcd\xd2\x90\xb6\x8aS\x9b{|k\xec\xcf\xa2NzI\x89+\xa1\x8f\xb6\x0c\x8b\xb7c\xcb\xbb#1ySC\xf4x\xfb\nl\xdd\xf6\x9a\xcc\xaf\xdfd\xb1\xe0\x82\xee\xdf)\xaf\xba\xb8\x9e^/\xa4$\x81\xbf\x8e\xadR>#\xa8\x9a\xa3\xd6\x1a\xee\xd8-\xb0\xf7\x8e:\x8d\x9bi\xfa\xed9\xd1\xe2\x93\xaa\xf8\xef>\x8fJ\x8b\xe8\xb4'
b'>_e<w\xf3a\xaeR\xfa\xa4/\x19_\'f|G \xfd&\xf4lY\xc3_\xe2\xc7:h&\xa0D!\xca$\xc5\xd2IL\x86\x00QHT+R\x0b\xf4\xfe\xa6+\x85\xd6\x90\x19\xbc(Z\x13\xac\x94\x070\x7f\x8d\xfa\x00D\r\x9f\xd5\x01\xaa9\xa2Z{\x18\x89r1A\x12\xb7T\xa8\x95 \x04\x066"\xfb-\xfdH\xc0\xc8\xe8CV\xf6\xd5\xa6\x91:l\xe6\xe5{fa\xa7L\xc6\xd3\xa7Y\x96\xb6m\x8a~\xe7\x8e\xd0\x11\xcd|\x19\xa5B\xf8I\x95\xdfve\xa0M\xbf\x8b(T\xdb\xc4\x8d\xad|\x14\x00\x93y\xe1j\x9d\xa0\x19\x04\xdd"\xdb\'\xe0(\xd1\xa0y\x0e\xcb1\x9b}\x9a\x13\n\xf9\xbe\xf3\x95<\xa9\x15\xb9~\xa8\t\xc3\xccW\x14'
b'\x12=\x04q\x9b\xb8\x1c\x10C\x02\x1e\x13`\xac>A\x9c\xf9\x9d\xc2\x83\xc2\xcd\x15\x97\x86\x8e\xd2\x85*s\r\x18~\x9b\xbai\xb1\x07\xacF\x0f\xfcrZ\xf1\xd0\x1f\xb0q\xe4\xbf\xd2\x87G\x1b\xdc\xd2u\x97\xb3\xcc?\xba\xba@\xae\x96\xdc\x1b\x10\xd3\x00f\nH\x99d\xf7{\xea \x82T\xf5\x03\x81\xd0:\r\x8d\xa6P\x92\xa0\x1d\x91n u6}:\x98\r\xa0\xbc\xe5\x84y\x01\x89\xa4P\xf4\xf9\xe4\xf2\x95\x8d\x85\x11\xfezN\x06- e(\x80\xd2\x01\x8e\x94&\xf7amQ\x08@\xd4w\x8e\xbbP\xfa\x17SECCON{being_able_to_s0lve_this_1s_great!}'
b'6P\xac\x03\x0f\xa0\xe0\xcd\xe0\x15\x1c\x82\xdc:\xe6\x0b\xbc\xfb\xa6Q\xc85\xd7V\x1f\xf0\x0e-\x13\xf4wX&HgZ\xc2kfb\xa9WC0s\xa9*\x19\xb9\x0b\xf9\xd4\x81"7E\x05n\x1eIC\xfb\x8e\xfc\xde]\x14\x1b\xd5\x1b\xad\xb9\xc8\xf7]\xc3\xa7\x8d\xed\x0fj\x9d\x99s\x7f\xc4\xfe\x1cqO\x82a\xb1\xf1\xe3\xfah\x84dx\x02\x03 t\xc3"o<\xfc\xc7\xa5\xed\xa1\xc2r\x1a=\xd6?\xa0\x8c\x8e\xd0\xc2>\xab\\\xeb\xa9\xec\xc9+\n\x8c\xfa3k\xa1\x17.:\x15\xeby\xdd\x8bV.\xec\xda\xc8\xe7\xa7\x19\x0c7Ys\xd1\x1c\rf\x91\xee\x9e\xbf\x1c\x11\x15Py\xad=\xaf\x82\xdd\x00s:#6\xb9F\xde\x1f\xf6\xdb\xdf\xda\xb4\x8f\xdd'
b"8\xdb\xcc\x88\x17\x03\x8d}1\xd3\x9f#\xdf\x8aB\xc4\xff\xd8x\xc0\xd6\x85\x96l0\\*\x96\xe8\xbeM\xc9\xb4\x97\x8e\x0cl\xa6e\x01\xd0\xb4\x975\xb0\xf0\x88{'\x87.\xa8\x00\xbbq\x9d\x08\xff\xca\xbdc\x08&oH\xa1\xc9\x92\xcf>;W\xc1l\x12\x00\xb1\xc1u\xb6\x97\xa3\x8fmL\xdb\xf9\xd8\xe0\xb7\x19\xd3{\x81\xa9\xed\xc9\xb6\xb5\xc7\x0b\x86\xa2\x14q3\x806+\x15\x80S\xb7Zyy\x92\xed\xa5\xb9\xf4V\x17\x05\x1e\x15\xd4\xde\xa3\xa5+A7\x88\t\t\x80']\xe7X\x88\x1e\x8d\xedm\tb\xd8\x15R\xd5\xb8\x9a\x95\xc9\x0eo\xd4\t\xc4\x12/\x06\xcc\xa5[\xa8\x17\x844\t\x8f=\x9b($\x886\x90\\|\x81\x81\x06\xb2!+\x03w\x1c("
b"0\xa8\x99E\xcby\x9cd\x9eh\x13;{\xa4\xa8\xed\xbdS\n\xd9\xf2\xbf{\xcea\xbdH\xdf\x1d@I\x9b|\x8d.\n\xf4l \x08\x9b\x7fi$\xeb\xb8|\xe8\xac3\x9e\x87|b\n:\x1a\x8b\xea\x07\xcb\x08\x15\xbc1\xfcbQ2\x94\x13\x1a\xe2\xb8j\rm\xa1\x80M\x98;\xa6\xc9kbH\\\x91\x8ez\xe3\xbd\xd7:\xaa\xaeWu\x15\xdf\xc5\xd1>]\xa9s\x8cu\xee\xb8\xd7\xe4,\xfc\xe3\tR\xa6\x98\xafm9K\x80\x96U^?K\x89\xc5[\x19\x9c~\xbecL\x9a\xa2\xcd\xfd6\x86\xff$b#Ea2E\xb3!\xf8\xd3~\xc1N\x17\x87'\n\xc6b\xdbY\xca\xe7#\x9e\xd0\x96\x97'[\x18\xe0\xed\x17:\xbcb\xae[p6Ww\x11\xf7"

:::

`SECCON{being_able_to_s0lve_this_1s_great!}`

### ふりかえり

* 問題設定には、すべて意味がある
- まずは基本のRSAを理解しよう
- 基本形からひねりを加えている理由を考えてみよう
* 煮詰まったときは、暗号/復号の定義に立ち戻ろう
- 場当たりで修正してもうまくいかない
- 紙とペンで、式変形をしっかりやろう
* 理屈がわかっても実装ができない...　使えるライブラリを把握しよう
- Pythonライブラリでできることは多い
- Sage.mathが使えるとなお良さげ