WaniCTF 2023 Crypto Writeup

## EZDORSA_Lv1
* 問題
    ```
    はじめまして！RSA暗号の世界へようこそ！
    
    この世界ではRSA暗号と呼ばれる暗号がいたるところで使われておる！
    
    それでは手始めに簡単な計算をしてみよう！
    
    p = 3
    q = 5
    n = p*q
    e = 65535
    c ≡ m^e (mod n) ≡ 10 (mod n)
    以上を満たす最小のmは何でしょう？
    FLAG{THE_ANSWER_IS_?}の？にmの値を入れてください。
    ```
* $m$ を小さい方から試す
* Solver
    ```py:solve.py
    p = 3
    q = 5
    n = p * q
    e = 65535
    c = 10
    
    for m in range(n):
        if pow(m, e, n) == 10:
            print(m)
    ```

## EZDORSA_Lv2
* 問題
    ```
    おや、eのようすが...?
    ```
* small e attack
* e の値が小さいので $m = c^{1/7}$ として計算すると得られる
* Solver
    ```py:solve.sage
    from Crypto.Util.number import *
    
    n = 25465155563758206895066841861765043433123515683929678836771513150236561026403556218533356199716126886534636140138011492220383199259698843686404371838391552265338889731646514381163372557117810929108511770402714925176885202763093259342499269455170147345039944516036024012941454077732406677284099700251496952610206410882558915139338028865987662513205888226312662854651278789627761068396974718364971326708407660719074895819282719926846208152543027213930660768288888225218585766787196064375064791353928495547610416240104448796600658154887110324794829898687050358437213471256328628898047810990674288648843902560125175884381
    e = 7
    c = 25698620825203955726406636922651025698352297732240406264195352419509234001004314759538513429877629840120788601561708588875481322614217122171252931383755532418804613411060596533561164202974971066750469395973334342059753025595923003869173026000225212644208274792300263293810627008900461621613776905408937385021630685411263655118479604274100095236252655616342234938221521847275384288728127863512191256713582669212904042760962348375314008470370142418921777238693948675063438713550567626953125
    
    c *= pow(5, -100, n)
    m = int(int(c)^(1/7))
    print(long_to_bytes(m))
    ```

## EZDORSA_Lv3
* 問題
    ```
    すうがくのちからってすげー！
    ```
* $\phi = (p_1 - 1)(p_2 - 1) \cdots (p_{100} - 1)$ として RSA を普通に復号する
* Solver
    ```py:solve.sage
    from Crypto.Util.number import *
    
    n = 22853745492099501680331664851090320356693194409008912025285744113835548896248217185831291330674631560895489397035632880512495471869393924928607517703027867997952256338572057344701745432226462452353867866296639971341288543996228186264749237402695216818617849365772782382922244491233481888238637900175603398017437566222189935795252157020184127789181937056800379848056404436489263973129205961926308919968863129747209990332443435222720181603813970833927388815341855668346125633604430285047377051152115484994149044131179539756676817864797135547696579371951953180363238381472700874666975466580602256195404619923451450273257882787750175913048168063212919624027302498230648845775927955852432398205465850252125246910345918941770675939776107116419037
    e = 65537
    c = 1357660325421905236173040941411359338802736250800006453031581109522066541737601274287649030380468751950238635436299480021037135774086215029644430055129816920963535754048879496768378328297643616038615858752932646595502076461279037451286883763676521826626519164192498162380913887982222099942381717597401448235443261041226997589294010823575492744373719750855298498634721551685392041038543683791451582869246173665336693939707987213605159100603271763053357945861234455083292258819529224561475560233877987367901524658639475366193596173475396592940122909195266605662802525380504108772561699333131036953048249731269239187358174358868432968163122096583278089556057323541680931742580937874598712243278738519121974022211539212142588629508573342020495
    
    factors = factor(n)
    phi = 1
    for f in factors:
        phi *= f[0] - 1
    
    d = pow(e, -1, phi)
    m = pow(c, d, n)
    print(long_to_bytes(int(m)))
    ```

## pqqp
* 問題
    ```
    ✨
    ```
* $s = p + q$ となっている  
    (証明)  
    $s = p^q + q^p \mod n$ となっているので，  
    $s \equiv q^p \pmod p$  
    $s \equiv p^q \pmod q$  
    よって $s$ は $s = pk + q = ql + p$ と表すことができる.  
    $p, q$ は互いに素なので $k-1 = qn$ とできて， $s = p(qn + 1) + q = pqn + p + q$ となるので $s \equiv p + q \pmod n$
* 法を $n$ としているのに $s$ が明らかに $n$ よりも小さいことからも気づける
* あとは $p + q = s, p q = n$ であることから解と係数の関係を使って  
    $$p, q = \frac{s \pm \sqrt{s^2 - 4n}}{2}$$  
として求められる
* Solver
    ```py:solve.sage
    from Crypto.Util.number import long_to_bytes
    
    n = 31091873146151684702346697466440613735531637654275447575291598179592628060572504006592135492973043411815280891993199034777719870850799089897168085047048378272819058803065113379019008507510986769455940142811531136852870338791250795366205893855348781371512284111378891370478371411301254489215000780458922500687478483283322613251724695102723186321742517119591901360757969517310504966575430365399690954997486594218980759733095291730584373437650522970915694757258900454543353223174171853107240771137143529755378972874283257666907453865488035224546093536708315002894545985583989999371144395769770808331516837626499129978673
    e = 65537
    c = 8684906481438508573968896111659984335865272165432265041057101157430256966786557751789191602935468100847192376663008622284826181320172683198164506759845864516469802014329598451852239038384416618987741292207766327548154266633297700915040296215377667970132408099403332011754465837054374292852328207923589678536677872566937644721634580238023851454550310188983635594839900790613037364784226067124711011860626624755116537552485825032787844602819348195953433376940798931002512240466327027245293290482539610349984475078766298749218537656506613924572126356742596543967759702604297374075452829941316449560673537151923549844071
    s = 352657755607663100038622776859029499529417617019439696287530095700910959137402713559381875825340037254723667371717152486958935653311880986170756144651263966436545612682410692937049160751729509952242950101025748701560375826993882594934424780117827552101647884709187711590428804826054603956840883672204048820926
    
    p = (s + sqrt(s^2 - 4 * n))//2
    q = n // p
    assert p * q == n
    
    phi = (p - 1) * (q - 1)
    d = pow(e, -1, phi)
    m = pow(c, d, n)
    print(long_to_bytes(int(m)))
    ```

## fusion
* 問題
    ```
    🧬
    ```
* $p$ と $q$ のビットが交互になったものが $r$
* 制約ソルバ z3 使えば解ける
* Solver
    ```py:solve.py
    from z3 import *
    from Crypto.Util.number import long_to_bytes
    
    n = 27827431791848080510562137781647062324705519074578573542080709104213290885384138112622589204213039784586739531100900121818773231746353628701496871262808779177634066307811340728596967443136248066021733132197733950698309054408992256119278475934840426097782450035074949407003770020982281271016621089217842433829236239812065860591373247969334485969558679735740571326071758317172261557282013095697983483074361658192130930535327572516432407351968014347094777815311598324897654188279810868213771660240365442631965923595072542164009330360016248531635617943805455233362064406931834698027641363345541747316319322362708173430359
    e = 65537
    c = 887926220667968890879323993322751057453505329282464121192166661668652988472392200833617263356802400786530829198630338132461040854817240045862231163192066406864853778440878582265466417227185832620254137042793856626244988925048088111119004607890025763414508753895225492623193311559922084796417413460281461365304057774060057555727153509262542834065135887011058656162069317322056106544821682305831737729496650051318517028889255487115139500943568231274002663378391765162497239270806776752479703679390618212766047550742574483461059727193901578391568568448774297557525118817107928003001667639915132073895805521242644001132
    r = 163104269992791295067767008325597264071947458742400688173529362951284000168497975807685789656545622164680196654779928766806798485048740155505566331845589263626813345997348999250857394231703013905659296268991584448212774337704919390397516784976219511463415022562211148136000912563325229529692182027300627232945
    
    s = Solver()
    p = BitVec('p', 1024)
    q = BitVec('q', 1024)
    s.add(p * q == n)
    for i in range(512):
        s.add(Extract(2 * i, 2 * i, p) == ((r >> (2 * i)) & 1))
        s.add(Extract(2 * i + 1, 2 * i + 1, q) == ((r >> (2 * i + 1)) & 1))
    
    if s.check():
        m = s.model()
        p = m[p].as_long()
        q = m[q].as_long()
        assert p * q == n
        phi = (p - 1) * (q - 1)
        d = pow(e, -1, phi)
        m = pow(c, d, n)
        print(long_to_bytes(m))
    else:
        print('UNSAT')
    ```

## DSA?
* 問題
    ```
    📨
    nc dsa-cry.wanictf.org 50010
    ```
* $s = mh + mxr \mod q$ と表すことができ，$m, x$ のビット幅がわかっていて，小さいので LLL が使える
* $m, x$ が未知で，それぞれ 232 ビットと 384 ビット
* $s, h, r, q$ は既知で，それぞれ 1024 ビット，256 ビット，1024 ビット，1024 ビット
* 格子基底行列を作る
    変数 $l$ を導入して $mh + mxr + ql - s = 0$ と式を変形できる．  
    $mx$ を一つの変数 (616 ビット) として見ると以下のように行列を構成できる．  
    ```math
    (m, mx, l, 1)
    \begin{pmatrix}
    h & 2^{384} & 0 & 0 \\
    r & 0 & 1 & 0 \\
    q & 0 & 0 & 0 \\
    -s & 0 & 0 & 2^{616} \\
    \end{pmatrix}
    = (0, m \cdot 2^{384}, mx, 2^{616})
    ```
    右辺の一番目の要素は 0 になってほしいので格子基底行列の 1 列目には $2^{2048}$ とかの大きな値をかける．  
    右辺は $mx$ が一番大きいので先頭以外は 616 ビットになるようにしている．
* Solver
    ```py:solve.sage
    from Crypto.Util.number import long_to_bytes
    
    p = 279190269876274251324426322312362714733335466785172094935419915241950478848265797905794448859598516635356219340992681163129868259377870067135628444717941906265805473582625356077252298182649372163332524356633146053976125545725650767983804894392935339017757208219447046253242656931615084883658404097001099730007
    q = 139595134938137125662213161156181357366667733392586047467709957620975239424132898952897224429799258317678109670496340581564934129688935033567814222358970953132902736791312678038626149091324686081666262178316573026988062772862825383991902447196467669508878604109723523126621328465807542441829202048500549865003
    g = 2
    y = 245099326491574331387969446501940775666603587742423152820598357159628365752045958025020038567706534672626748169842987318014617545613363501949530539620123466687508860974930130416906502772493921476659399272182211480517540148673992560551242133008378923784438789116801129536524502657695170230180310349262064209980
    FLAG = '*****************************'
    h = int('7aad5b407493e83e9c8a11170733019dfb55dcdb0b7ec677ded13ad9ab16cc82', 16)
    r = 61401707010758101526146375076142785590307812475121812316952376486069149360425245868500855973757366554075933599220935059105890347272857469593141580674416812501978293803766670329096383435341545996560650936693344739955943829806575705777357363320849419106573553984283202966428145927420324135463723534658578592614
    s = 48637021331665511272513214633202984902204322589333295589859019169751254104682683392761107717092909357795323317692328312017253860170966811015512252032028696767895780237038940801877091113791000912163486487635395394503581136734231195693995178942974771893278056379715813151417596619896517355745775698570054210954
    
    b = len(FLAG) * 8
    N = 2^2048
    mat = [
        [h * N, 2^(8 * 48), 0, 0],
        [r * N, 0, 1, 0],
        [q * N, 0, 0, 0],
        [-s * N, 0, 0, 2^(b + 8 * 48)]
    ]
    ans_mat = Matrix(ZZ, mat).LLL()
    for ans in ans_mat:
        if ans[0] == 0 and abs(ans[-1]) == 2^(b + 8 * 48):
            m = abs(ans[1]) // (2^(8 * 48))
            print(long_to_bytes(int(m)))
    ```