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
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
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
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
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
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 ビット) として見ると以下のように行列を構成できる．右辺の一番目の要素は 0 になってほしいので格子基底行列の 1 列目には $2^{2048}$ とかの大きな値をかける．(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})
右辺は $mx$ が一番大きいので先頭以外は 616 ビットになるようにしている． - Solver
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)))