huangx607087学习ECC的笔记4
最近更新时间:2025.2.8 16:00,第 5 次更新
Reference:鸡块佬的blog ,awda的blog
0.About BlockCipher3:2021.09.04,BlockCiphser4:2024.11.06,中间38个月
LatticeNotes7:2021.07.25,LatticeNotes8:2024.12.05,中间41个月
然后,ECCNotes,经过47个月,也要更新了。。。回顾了以下之前写的,满头问号:我之前写了啥?还好,看了2h,看懂了。。。
ECCNotes
发布时间
主要内容
$1$
$2021.02.21$
椭圆曲线基本知识
$2$
$2021.03.04$
椭圆曲线的双线性对(1)
$3$
$2021.03.25$
椭圆曲线上的除式、广播攻击和相关明文攻击
$4$
$2025.02.01$
椭圆曲线上的同源,SIDH
究其原因,是因为之前0xGame2024 Week4出了个SIDH,当时完全看不懂,那边wp写得也挺简陋的。并且感觉最近多项式、同态这些玩意在CTF中出现得越来越多(盲猜dbt佬读博研究方向的就是多项式啥的,然后出了好多多项式的题)。
特别提醒:本文内容均为 “测代码测出来” 的,没有给复杂的证明,因为复杂度证明我自己都看不懂。。。SIDH和CSIDH的论文我其实都看了一下,但有些知识真的很晦涩难懂。。因此最终还是选择使用测代码的方式来给出结论。
那么今天这个就以SIDH入手介绍同源吧,先给个0xGame2024 Week4的题目代码,后面就围绕着这个代码了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 from random import randintfrom secret import flag ea, eb = 110 , 67 p = 2 **ea*3 **eb - 1 F.<i> = GF(p**2 , modulus=[1 ,0 ,1 ]) E0 = EllipticCurve(F, [1 ,0 ]) PA = E0.random_point() QA = E0.random_point() sA = randint(0 , 2 **ea) RA = PA + sA*QAprint (f'RA = {RA.xy()} ' ) RB_= [int (i) for i in input (f'[+] Give me RB:\n>' ).split(',' )] RB = E0(RB_[0 ]*i + RB_[1 ], RB_[2 ]*i + RB_[3 ]) phi_B = E0.isogeny(RB, algorithm='factored' ) E_B = phi_B.codomain()assert E_B.is_isogenous(E0) R_share = phi_B(PA) + sA * phi_B(QA) phi_share = E_B.isogeny(R_share, algorithm='factored' ) secret = phi_share.codomain().j_invariant() secret_ = [int (i) for i in input ('[+] Tell me the secret\n>' ).split(',' )] secret_ = secret_[0 ] * i + secret_[1 ]if secret_ == secret: print (f'[+] flag:{flag} ' )else : print ('[+] Wrong' )
1. SIDH预备知识 1.1 超奇异曲线 超奇异曲线:若模 $p$ 下的椭圆曲线 $E$ 的阶满足 $\mathrm{ord}(E)\equiv 1\pmod p$ ,则 $E$ 是超奇异曲线
1 2 3 4 5 6 7 8 p=71 C71.<img>=GF(71 **2 ,modulus=[1 ,0 ,1 ]) E1=EllipticCurve(C71,[7 ,2 ]) E2=EllipticCurve(C71,[11 ,9 ])print (E1.order() % p , E1.is_supersingular(),E1.j_invariant())print (E2.order() % p , E2.is_supersingular(),E2.j_invariant())
1.2 j-不变量 1.2.1 j-不变量的定义 如果 2 个曲线 $E_1$ 和 $E_2$ 具有相同的 j-不变量,则两条曲线同构。
设 $\mathbb C_{71}=\mathbb Z_{71}+\mathrm i\mathbb Z_{71}$ ,其中 $\mathrm i^2\equiv -1\pmod{71}$,则定义在 $\mathbb C_{71}$ 上的超奇异曲线有 以下 $7$ 个j-不变量,或者说,若 $\mathbb C_{71}$ 上某个椭圆曲线的j-不变量为下面的数值中的某个,则这条曲线是超奇异曲线。
1 [0, 17, 24, 40, 41, 48, 66]
如果 $p=431$,则对应的超奇异曲线上会有 $37$ 个 j-不变量,如下所示:
1 [0 , 4 , 19 , 61 , 67 , 102 , 107 , 125 , 143 , 150 , 189 , 234 , 241 , 242 , 316 , 319 , 356 , 358 , 381 , 419 , 422 , 81 *img + 65 , 350 *img + 65 , 209 *img + 118 , 222 *img + 118 , 42 *img + 141 , 389 *img + 141 , 87 *img + 190 , 344 *img + 190 , 67 *img + 304 , 364 *img + 304 , 132 *img + 315 , 299 *img + 315 , 106 *img + 379 , 325 *img + 379 , 125 *img + 426 , 306 *img + 426 ]
扩展到任意 $p$,则 j-不变量的个数为 $\left\lfloor\dfrac{p}{12}\right\rfloor+z$ 个,其中 $z$ 的取值为 $0,1,2$,与 $p$ 的值有关。
1.2.2 j-不变量与同构 我们设: $E_1:y^2\equiv x^3+7x+2\pmod{71}$ 和 $E_2:y^2\equiv x^3+11x+52\pmod {71}$ 的 j-不变量均为 $66$,因此这两条曲线均为 $\mathbb C_{71}$ 上的超奇异曲线,且满足同构性质,同构表达式为: $$ \phi:E_1(x,y)\rightarrow E_2(23x,20\mathrm iy) $$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 p=71 C71.<img>=GF(71 **2 ,modulus=[1 ,0 ,1 ]) E1=EllipticCurve(C71,[7 ,2 ]) E2=EllipticCurve(C71,[11 ,52 ]) f = E1.torsion_polynomial(1 ).monic() phi=EllipticCurveIsogeny(E1,f,E2) phi.rational_maps() k=randint(1 ,p) G=E1.random_element() G2=G*k x,y=G.xy() x,y=23 *x,20 *img*y H=E2(x,y) H2=H*k H2.x()/G2.x(),H2.y()/G2.y()
再举一个 $\mathbb C_{431}$ 上的例子,两条曲线分别为 $E_1:y^2=x^3+(208\mathrm i+161)x^2+x$ 和 $E_2:y^2=x^3+(172\mathrm i+162)x^2+x$,其映射为: $$ \phi:E_1(x,y)\rightarrow E_2(\left(\left(66 \mathrm{i} + 182\right) x + 300 \mathrm{i} + 109, \left(122 \mathrm{i} + 159\right) y\right) ) $$
1 2 3 4 5 6 7 8 9 from random import * p=431 C431.<img>=GF(p**2 ,modulus=[1 ,0 ,1 ]) E1=EllipticCurve(C431,[0 ,208 *img+161 ,0 ,1 ,0 ]) E2=EllipticCurve(C431,[0 ,172 *img+162 ,0 ,1 ,0 ]) f = E1.torsion_polynomial(1 ).monic() phi=EllipticCurveIsogeny(E1,f,E2) phi.rational_maps()
当然adwa告诉我有更简单的办法:
1 2 3 4 5 6 7 8 p=71 C71.<img>=GF(71 **2 ,modulus=[1 ,0 ,1 ]) E1=EllipticCurve(C71,[7 ,2 ]) E2=EllipticCurve(C71,[11 ,52 ]) phi=E1.isomorphism_to(E2)print (phi.rational_maps())
1.3 蒙哥马利曲线 之前我们在密码学中常用的曲线形式为 $y^2=x^3+ax+b$,但其实椭圆曲线的完整表达形式为 $y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6$。而蒙哥马利曲线的表达式为 $y^2=x^3+ux^2+x$。
感谢@adwa 的指正,之前一个版本误写成了 $x^3+ux+x$
注意这里 $x$ 的系数为 $1$,而新增加的 $x^2$ 的系数可以变动,和之前的曲线相比,可以发现 $(0,0)$ 一定在蒙哥马利曲线上。
对于蒙哥马利曲线而言,其 j-不变量可以快速计算为 $j(Em)=\dfrac{256(u^2-3)^3}{u^2-4}$。对于两个j-不变量相同的蒙哥马利曲线,它们之间的同态映射中表达式中不会出现分母。(1.2.2的两个例子)。
当然,常用曲线和蒙哥马利曲线之间的交集为 $y^2=x^3+x$,这对应的是 $u=0,b=0$ 的情况,该曲线也多用于SIDH中。当然,任意形式的椭圆曲线都可以转化为与其j-不变量相同的蒙哥马利曲线形式,在Sagemath中,可以调用 E.montgomery_model()
实现。在1.9.4中的代码中,可以验证这一性质。
为了简化问题,我们定义曲线 $E$ 的蒙哥马利参数为 $E$ 的蒙哥马利形式中年的 $u$ 值,Sage中可以使用 E.montgomery_model().a2()
实现。
1.4 同源 1.4.1 倍点同构映射 刚才我们其实已经接触到了同源的概念,但我们以”同构”去描述的(呃,因为信安数基中讲的是同构),但事实上,同构是同源的特殊情况。在之前的同构映射中,也可以使用一个看似trivial的方法,自己跟自己的二倍点映射:
1 2 3 4 5 6 7 8 9 10 11 12 13 from random import * p=71 Cp.<img>=GF(p**2 ,modulus=[1 ,0 ,1 ]) E=EllipticCurve(Cp,[1 ,0 ])print (E._multiple_x_numerator(2 ))print (E._multiple_x_denominator(2 )) phi = E.scalar_multiplication(2 )print (phi.rational_maps()[0 ])print (phi.rational_maps()[1 ])
这里的映射结果为:
$$ \phi:(x,y)\rightarrow\left(\frac{x^{4} + 69 x^{2} + 1}{4 x^{3} + 4 x}, \frac{8 x^{6} y + 40 x^{4} y + 31 x^{2} y + 63 y}{64 x^{6} + 57 x^{4} + 64 x^{2}}\right) $$
如果我们令 $x$ 的分母 $4x^3+4x=0$,也就是 $x^3+x=0$,那么可以得到 $x=0,\mathrm i,-\mathrm i$。可以利用 division_points
去实现,相当于有限域开 $n$ 次根。
1 2 3 L=(E(0 ).division_points(2 ))print (L)
由于 $E$ 的阶为 $72$,那么也一定存在阶为 $3$ 的情况(显然,如果 $P$ 的阶为 $3$,那么 $-P$ 的阶也是 $3$),那么也存在某个点和自己的三倍点映射:
1 2 3 4 5 print (E._multiple_x_denominator(3 ).monic()) L=(E(0 ).division_points(3 ))print (L)
解方程 $x^8 + 4x^6 + 27x^4 + 46x^2 + 8=0$,可以得到对应的解为 $±\sqrt{±\frac{1}{2} \sqrt{±2 \sqrt{497} - 42} - 1}$,这个解在 $\mathbb C_{71}$ 中就变成了 $2,69,19\mathrm i,52\mathrm i$,此时的映射表达式如下(已经开始复杂了!) $$ \phi:(x,y)\rightarrow\left(\frac{x^{9} + 59 x^{7} + 30 x^{5} + 36 x^{3} + 9 x}{9 x^{8} + 36 x^{6} + 30 x^{4} + 59 x^{2} + 1} ,\frac{18 x^{12} y + 41 x^{10} y + 12 x^{8} y + 48 x^{6} y + 7 x^{4} y + 13 x^{2} y + 17 y}{60 x^{12} + 5 x^{10} + 21 x^{8} + 27 x^{6} + 64 x^{4} + 40 x^{2} + 53} \right) $$ 对于阶为 $l$ 的点,也就是满足 $lP=\mathcal O$ 的点构成的集合,我们可以叫做 $l$-torsion。也可以把这个集合记为 $\ker(l)$,有 $\ker(l)$ 与 $\mathbb Z_{l+1}^2$ 同构。若 $l$ 为素数,则可以构成 $l+1$ 个阶为 $l$ 的循环子群,且两个不同子群之间的元素是线性无关的。
$\ker(2)$ 和 $\ker(3)$ 的结构如下图所示,中间是无穷远点 $\mathcal O$。这个花瓣形的结构,貌似在之前导师发给我的双线性对那个PPT上见过。
1.4.2 同源在Sage中的实现 可以使用Sage来实现同源,这里选择了 $(69,9\mathrm i)$ 作为同源映射,可以看到, $E_1$ 的 j-不变量为 $24$,而 $E_2$ 的 j-不变量为 $66$。说明 $E_2$ 与 $E_1$ 并不是同构的。而我们刚才说过,同源的一种特殊情况是同构,同构是只有一个核元素 $\mathcal O$ 的同源,因此这里只有 $E_1$ 和 $E_2$ 同源,没有 $E_1$ 和 $E_2$ 同构。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 from random import * p=71 Cp.<img>=GF(p**2 ,modulus=[1 ,0 ,1 ]) E1=EllipticCurve(Cp,[1 ,0 ])print (E1.j_invariant()) A = E1(69 ,9 *img) phi = E1.isogeny(A) E2 = phi.codomain()print (E2)print (E2.j_invariant())print (phi.rational_maps()[0 ])print (phi.rational_maps()[1 ])
1.4.3 同源图 如果我们把 $\mathbb C_{71}$ 上的 $7$ 个 超奇异 j-不变量各构造一条曲线,并取每条曲线上 $\ker (2)$ 中的三个点(不包括 $\mathcal O$)进行同源,可以得到这样的一个图。在这边,按理说每个点的度都应该是 $3$,但由于存在自环和重边,当然也有特殊情况,因此只有一个点的度是 $3$。比如 $40$ 连接的三条边,说明 j-不变量为 $40$ 的曲线中, $\ker(2)$ 中的三个非无穷远点经过同源,得到的新的同源曲线的 j-不变量可能是 $48,0,17$。
当然,可以发现,这是一个无向图,因为同源是对偶的,也就是说,j-不变量为 $40$ 的曲线可以同源到 j-不变量为 $48$ 的曲线,反过来,也存在 j-不变量为 $48$ 的曲线同源到 j-不变量为 $40$ 的曲线上去。而对于一条路径 $40\rightarrow48\rightarrow 66$ 而言,这相当于两次度为 $2$ 的的同源,也可以视为一次 度为 $4$ 的同源。
这个是 $p=431$ 的 $\ker(2)$ 同源图,由于这里的j-不变量有 $73$ 个,因此度为 $3$ 的点占了大多数。当然,也可以选择 $\ker(3)$ 进行度为 $3 $ 的同源,那么每个点的度就是 $4$ 了,得到的图也会与 $\ker(2)$ 得到的图不一样。
1.9 总结和回顾 1.9.1 Sage求j不变量的方法 1 2 3 E=EllipticCurve(GF(163 ),[145 ,49 ]) E.j_invariant()
1.9.2 判断一个曲线是不是超奇异曲线 超奇异曲线的定义:对于定义在 $\mathbb F_{p^k}$ 上的曲线$E$ ,满足 $|E|\equiv 1 \pmod p$ 的曲线,也就是每个点的阶除以 $p$ 的余数均为 $1$ 的曲线。
判断方法:E.is_supersingular()
CryptoHack上的例题:在一堆 $A$ 中找到满足超奇异椭圆曲线的 $A$。
1 2 3 4 5 6 7 8 9 10 11 p = 2 **127 - 1 F = GF(p) A_coefficients = [42066522414747786381920855365597565167 , 134737796133950768030018008799183714450 , 91227728321286829861377337128366199392 , 36028658925231693144107803298680870937 , 76980490750956259225056736203333999910 , 126464584711216077690137140186180693785 , 120907192356535756729244966659175101927 , 2073101923485307949792397315592577773 , 106605223173829520914696961378825556644 , 132050324183446216441182346564708456430 , 124925153504327803154756555702421815457 , 77660524902287384914209674976778162880 , 16925059684259068279300282630403302492 , 132526617782398476874569966601318594117 , 37496280130274706477358606089317978157 , 91534360167274359091293339760566159682 , 120709879291518822698484419346768523476 , 65363777855209839999210042121004357333 , 55967872730073787267488839585941569643 , 36898228725344658691223127152754689708 , 154541377159837330781469948056573864248 , 13491755064214040906252463281637003507 , 108942779083954481764769642529914352298 , 148339474803908132859207234892176688872 , 52779580168403190690189094462689129092 , 133118771370904939228695413069672106301 , 37742029987768224512401633920499017927 , 83070983011286908751419953762864350804 , 27579898547487494629585968117425586134 , 115653129582046969888509682678358651292 , 101704360405093002365341608151788197801 , 26577867537091108935632327578899771513 , 63823008561770200181128212771463569059 , 65567745784333136215045519526981712608 , 94067826399698019061457587710503262758 , 157599028084077522633805211440852474188 , 50964910790177922795145482477309765050 , 120922548311156791677654872844569348131 , 59168891682494541493872447445083865177 , 147837049250659841035474307770567756447 , 13642843499473036336330049788238558798 , 45666199191182278515747915944910919562 , 103074928257298029070114474733055407882 , 16962967100651145532896179458853429025 , 154909948485415956842534840410675083382 , 22820775199676215898647235824150575751 , 154329269756413993112920009420869474380 , 138300956197972238000951467341005201893 , 166046660427895907846214752672019787536 , 141774513481148066771761235501253922565 , 124404668777350018566758645287948962779 , 141710390876873989703209183888838141129 , 43383267258553897726444281302908756439 , 8382163174802298716075674661700526105 , 42647418827645100430740897684493106281 , 115369337788739564019292557470108514746 , 51602469273125266568465673976482373008 , 21274053188388536879722524326434447058 , 155399839214546532918143677492979875025 , 134844799136804904273265536589445951710 , 170141183460469230846243588177825628225 , 34714351369438188536819236204585680389 , 106014160818648567132647832826887771006 , 26341808657057110683680629380277446393 , 98549712359055082009930885194365045772 , 143002488899264107138574246913562763245 , 83199987237136698285155302750237377917 , 163678062518962214263756137167913332057 , 107703968966152189273001348451115931501 , 154459054255799385370678297918227508273 , 160394354920882308230455249642244327876 , 63082984734540825428754448178295870172 , 158310155193384062203205713864649469386 , 156168266884432986041374465845782494518 , 110147569271988413629697268109820438653 , 60009165402929810599765761482393291600 , 160471809661117354771700362601108099823 , 70205649924045989651475317850057844161 , 44696813017317041212253313033993441039 , 45036886626031031391784472846348343968 , 77934017380754619764511795264587760758 , 23111293661357074492564163833427567827 , 39989430534767072035052164998617514373 , 435384467928024061094999646205823086 , 109651347199199233302113859638926694534 , 140233796564908846498304362688605532781 , 159429449304855699713742269141196048727 , 84378534640632088318459736438433440511 , 35039618806759555128366649831062612185 , 94527269434501797889731458720771789225 , 161408562964041668171049211002143456626 , 3870684416023152928311974603228368345 , 28196517242154639492840099181523267155 , 99806088062582844867731983345213108996 , 53032136485981165230199947023828963494 , 108846135438150868833980774050157615416 , 111171383309545532264862195892560386067 , 56167964140714208429900388258541421783 , 133956857210332500232234627352247869689 , 105983790995194300223960924968597095964 ]for A in A_coefficients: E = EllipticCurve(F, [0 , A, 0 , 1 , 0 ]) if (E.is_supersingular()): print (A)
1.9.3 同源的性质 由于同源性不仅是曲线之间的有理映射,而且还是保留这些曲线上的群结构的映射。因此,即使 $\phi:E\rightarrow E’$ 未知,如果我们已经知道了 $E’$ 上的两个点 $\phi(P),\phi(Q)$,仍然可以高效地计算 $\phi(P+Q)=\phi(P)+\phi(Q)$ 和 $\phi(kP)=k\phi(P)$。
CryptoHack Problem 3:假设我们知道 $p=63079$,$\phi(P)=(48622,27709),\phi(Q)=(9460,13819)$,那么我们可以直接解出曲线 $E’:y^2=x^3+ax+b$ 的参数 $a,b$,随后直接计算 $\phi(P+Q)=\phi(P)+\phi(Q)$。
1 2 3 4 5 6 7 8 9 10 11 P=(48622 ,27709 ) Q=(9460 ,13819 ) p=63079 var("a b" ) solve([P[1 ]**2 ==P[0 ]**3 +a*P[0 ]+b,Q[1 ]**2 ==Q[0 ]**3 +a*Q[0 ]+b],[a,b]) A=GF(p)(-19016674762988 /6527 ) B=GF(p)(174373293256389527 /6527 ) E=EllipticCurve(GF(p),[A,B]) (E(P)+E(Q)).xy()
1.9.4 求一个曲线的蒙哥马利曲线形式 1 2 3 4 5 6 7 8 9 10 E=EllipticCurve(GF(1912812599 ),[312589632 ,654443578 ]) E.montgomery_model()print (E.montgomery_model())print (E.montgomery_model().a2())print (E.j_invariant())print (E.montgomery_model().j_invariant())
1.9.5 同源上的离散对数问题 由于同源中所用的模数 $p$ 满足 $p-1$ 光滑或 $p+1$ 光滑,因此可以在这里解离散对数,来看这样一个题:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 import osfrom Crypto.Cipher import AESfrom Crypto.Hash import SHA256from Crypto.Util.Padding import pad proof.all (False ) FLAG = b"crypto{?????????????????????????????????????????????????????????????}" p = 2 **127 - 1 F.<i> = GF(p^2 , modulus=[1 ,0 ,1 ]) E = EllipticCurve(F, [1 ,0 ]) P, Q = E.gens() a = randint(0 , p) | 1 b = randint(0 , p) | 1 c = randint(0 , p) | 1 d = randint(0 , p) | 1 R = a*P + b*Q S = c*P + d*Qdef encrypt_flag (a, b, c, d ): data_abcd = str (a) + str (b) + str (c) + str (d) key = SHA256.new(data=data_abcd.encode()).digest()[:128 ] iv = os.urandom(16 ) cipher = AES.new(key, AES.MODE_CBC, iv) ct = cipher.encrypt(pad(FLAG, 16 )) return iv.hex (), ct.hex () iv, ct = encrypt_flag(a, b, c, d)print (f"{P = } " )print (f"{Q = } " )print (f"{R = } " )print (f"{S = } " )print ()print (f"{iv = } " )print (f"{ct = } " )
方法1 很明显,我们要求出 $a,b,c,d$ 的值,才能够解出flag。但这个椭圆曲线上的生成元有两个,因此直接调用离散对数是不太现实的,可以利用同源,比如 phi1=E.isogeny(P)
后,有 $\phi_1(P)-\mathcal O$,相当于同源之后,新的曲线 $E_1$ 上的点经过 $\phi_1$,实现了对 $P$ 进行了”取模”操作。
不过sagemath似乎直接调用会报错,考虑到阶是光滑的,偷一个PoligHellman的代码,改一下就OK了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 p = 2 **127 - 1 F.<i> = GF(p**2 , modulus=[1 ,0 ,1 ]) E = EllipticCurve(F, [1 ,0 ]) P = E(24722427318870186874942502106037863239 *i + 62223422355562631021732597235582046928 , 66881667812593541117238448140445071224 *i + 149178354082347398743922440593055790802 ) Q = E(136066972787979381470429160016223396048 *i + 52082760150043245190232762320312239515 , 37290474751398918861353632929218878189 *i + 89777436105166947842660822806860901885 ) R = E(115434063687215369570994517493754451626 *i + 158874018596958922133589852067300239562 , 62259011436032820287439957155108559928 *i + 81253318200557694469168638082106161224 ) S = E(42595488035799156418773068781330714859 *i + 113049342376647649006990912915011269440 , 25404988689109287499485677343768857329 *i + 125117346805247292256813555413193592812 ) iv = '6f5a901b9dc00aded4add3791812883b' ct = '56ecb68a90cad9787a24a4511720d40d625901577f6d0f1eef9fc34cf042709110cdc061fff91e934877674a30ed911283b83927dbcc270ae358d6b1fe2d5bed18ce1b02d8805de55e5b36deb0d28883' def PoligHellman (G,Y,order ): factors, exponents = zip (*factor(order)) temp=[] for i in range (len (factors)): q=factors[i] a=[] for j in range (1 ,exponents[i]+1 ): GG=G*(order//q**j) YY=Y*(order//q**j) for k in range (q): s=0 for t in range (len (a)): s+=a[t]*q^t s+=k*q^(len (a)) if s*GG==YY: a.append(k) break x_q=0 for j in range (len (a)): x_q+=a[j]*q^j temp.append(x_q) f=[] for i in range (len (factors)): f.append(factors[i]**exponents[i]) return crt(temp,f) n=P.order() phi1,phi2=E.isogeny(P,algorithm='factored' ),E.isogeny(Q,algorithm='factored' ) E1,E2=phi1.codomain(),phi2.codomain() a=PoligHellman(phi2(P),phi2(R),p+1 ) b=PoligHellman(phi1(Q),phi1(R),p+1 ) c=PoligHellman(phi2(P),phi2(S),p+1 ) d=PoligHellman(phi1(Q),phi1(S),p+1 )print (a,b,c,d)assert (a*P+b*Q==R and c*P+d*Q==S)from hashlib import sha256from Crypto.Cipher import AES key = sha256((str (a)+str (b)+str (c)+str (d)).encode()).digest()[:128 ] aes = AES.new(key, AES.MODE_CBC, bytes .fromhex(iv))print (aes.decrypt(bytes .fromhex(ct)))
update:这么做也可以,但必须指定 operation='+'
1 discrete_log(phi1(R),phi1(Q),operation='+' )
方法2 当然,也可以使用双线性对的知识,由于 $R=aP+bQ$,可以使用weil_pairing求解,得到: $$ e(R,Q)=e(aP+bQ,Q)=e(aP,Q)e(bQ,Q)=e(P,Q)^a $$ 同理: $$ e(P,R)=e(P,aP+bQ)=e(P,aP)e(P,bQ)=e(P,Q)^b $$ 这样 $a,b$ 就可以通过离散对数解出来了,同理解得 $c,d$,这样就不需要用同源的知识了!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 p = 2 **127 - 1 F.<i> = GF(p**2 , modulus=[1 ,0 ,1 ]) E = EllipticCurve(F, [1 ,0 ]) P = E(24722427318870186874942502106037863239 *i + 62223422355562631021732597235582046928 , 66881667812593541117238448140445071224 *i + 149178354082347398743922440593055790802 ) Q = E(136066972787979381470429160016223396048 *i + 52082760150043245190232762320312239515 , 37290474751398918861353632929218878189 *i + 89777436105166947842660822806860901885 ) R = E(115434063687215369570994517493754451626 *i + 158874018596958922133589852067300239562 , 62259011436032820287439957155108559928 *i + 81253318200557694469168638082106161224 ) S = E(42595488035799156418773068781330714859 *i + 113049342376647649006990912915011269440 , 25404988689109287499485677343768857329 *i + 125117346805247292256813555413193592812 ) iv = '6f5a901b9dc00aded4add3791812883b' ct = '56ecb68a90cad9787a24a4511720d40d625901577f6d0f1eef9fc34cf042709110cdc061fff91e934877674a30ed911283b83927dbcc270ae358d6b1fe2d5bed18ce1b02d8805de55e5b36deb0d28883' n=P.order()def ee (A,B ): return A.weil_pairing(B,n) a=discrete_log(ee(R,Q),ee(P,Q)) b=discrete_log(ee(P,R),ee(P,Q)) c=discrete_log(ee(S,Q),ee(P,Q)) d=discrete_log(ee(P,S),ee(P,Q))print (a,b,c,d)assert (a*P+b*Q==R and c*P+d*Q==S)from hashlib import sha256from Crypto.Cipher import AES key = sha256((str (a)+str (b)+str (c)+str (d)).encode()).digest()[:128 ] aes = AES.new(key, AES.MODE_CBC, bytes .fromhex(iv))print (aes.decrypt(bytes .fromhex(ct)))
2.SIDH算法 2.1 算法流程 在上面的基础知识下,我们开始介绍 SIDH 算法
1.双方选择模数 $p=2^\alpha3^\beta k-1$,其中尽量使 $2^{\alpha}≈3^{\beta}$,$k$ 通常取 $1$。和一条 $\mathbb C_{p}$ 上的超奇异椭圆曲线(一般为 $y^2=x^3+x$)。此处我们选择 $p=71=2^{3}3^{2}-1$ ,$E:y^2=x^3+x$ 在 $\mathbb C_{p}$ 上的 j-不变量为 $24$。
1 2 3 4 5 from random import * ea,eb=3 ,2 p=2 **ea*3 **eb-1 Cp.<img>=GF(p**2 ,modulus=[1 ,0 ,1 ]) E=EllipticCurve(Cp,[1 ,0 ])
2.A选择 $E$ 上阶为 $2^\alpha$ 的两个线性无关的点 $P_A,Q_A$ (可以发现 $E$ 上有两个阶为 $72$ 的生成元,因此相对来说还是比较容易取到的),同理,B选择 $E$ 上阶为 $3^\beta$ 的两个线性无关的点 $P_B,Q_B$。判断 $P,Q$ 线性无关的方法,就是双线性对 $e(P,Q)$ 的值不为 $1$,也就是 $Q$ 无法写成 $kP$ 的形式。双方分别公开 $P_A,Q_A,P_B,Q_B$ 作为公共参数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 from random import *def genA (Ec ): while (1 ): Pa=Ec.random_element()*((p+1 )//2 **ea) if (Pa!=E(0 ) and Pa.order()==2 **ea): break while (1 ): Qa=Ec.random_element()*((p+1 )//2 **ea) if (Qa.weil_pairing(Pa,2 **ea)!=1 and Qa.order()==2 **ea): break return Pa,Qadef genB (Ec ): while (1 ): Pb=Ec.random_element()*((p+1 )//3 **eb) if (Pb!=E(0 ) and Pb.order()==3 **eb): break while (1 ): Qb=Ec.random_element()*((p+1 )//3 **eb) if (Qb.weil_pairing(Pb,3 **eb)!=1 and Qb.order()==3 **eb): break return Pb,Qb Pa,Qa=genA(E) Pb,Qb=genB(E)print (Pa.xy(),Qa.xy(),Pa.weil_pairing(Qa,2 **ea))print (Pb.xy(),Qb.xy(),Pb.weil_pairing(Qb,3 **eb))
3.A随机选择秘密值 $x_A$,计算 $S_A=P_A+x_AQ_A$。然后计算同源 $\phi_A:E\rightarrow E_A$,其中 $\phi_A$ 为 $\alpha-1$ 个 $2$ 次同源组合而成,最终结果与 $S_A$ 相关。因此,我们得到 A 的公钥为 $E_A,\phi_A(P_B),\phi_A(Q_B)$,私钥为 $x_A,S_A$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 xa=randint(2 ,2 **ea-1 ) Sa=Pa+xa*Qaprint (xa,Sa.xy()) Sa1=Sa E1=E Pas,Eas=[],[E]for i in range (ea-1 ,0 ,-1 ): Ta=Sa1*(2 **i) phi = E1.isogeny(Ta) Eai = phi.codomain() Sa1 = phi(Sa1) E1=Eai Pas.append(phi) Eas.append(Eai) phiA=Pas[-1 ]for i in range (len (Pas)-2 ,-1 ,-1 ): phiA*=Pas[i]print (phiA)for i in range (len (Eas)): print (Eas[i].j_invariant(),end=' -> ' if i!=len (Eas)-1 else '\n' )""" Output: 6 (20*img + 58, 45*img + 24) Composite morphism of degree 4 = 2^2: From: Elliptic Curve defined by y^2 = x^3 + x over Finite Field in img of size 71^2 To: Elliptic Curve defined by y^2 = x^3 + 27*x + 41 over Finite Field in img of size 71^2 24 -> 24 -> 17 """
4.同理,B随机选择秘密值 $x_B$,计算 $S_B=P_B+x_BQ_B$。然后计算同源 $\phi_B:E\rightarrow E_B$,其中 $\phi_B$ 为 $\beta-1$个 $3$ 次同源组合而成,最终结果与 $S_B$ 相关。因此,我们得到 B 的公钥为 $E_B,\phi_B(P_A),\phi_B(Q_A)$,私钥为 $x_B,S_B$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 xb=randint(2 ,3 **eb-1 ) Sb=Pb+xb*Qbprint (xb,Sb.xy()) Sb1=Sb E1=E Pbs,Ebs=[],[E]for i in range (eb-1 ,0 ,-1 ): Tb=Sb1*(3 **i) phi = E1.isogeny(Tb) Ebi = phi.codomain() Sb1 = phi(Sb1) E1=Ebi Pbs.append(phi) Ebs.append(Ebi) phiB=Pbs[-1 ]for i in range (len (Pbs)-2 ,-1 ,-1 ): phiB*=Pbs[i]print (phiB)for i in range (len (Ebs)): print (Ebs[i].j_invariant(),end=' -> ' if i!=len (Ebs)-1 else '\n' )""" 6 (54, 18) Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field in img of size 71^2 to Elliptic Curve defined by y^2 = x^3 + 13*x + 66 over Finite Field in img of size 71^2 24 -> 66 """
5.此时,双方的公钥如下,并且在上面的输出中,我们可以看到,A 共存储了 $\alpha=3$ 条曲线,这三条曲线的j-不变量分别为:$24,24,17$,B存储了 $\beta=2$ 条曲线,其 j-不变量分别为 $24,66$。(双方第一个 $24$ 为原始曲线)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 PKA=(phiA.codomain(),phiA(Pb),phiA(Qb)) PKB=(phiB.codomain(),phiB(Pa),phiB(Qa))print (PKA)print (PKB)""" PKA: (Elliptic Curve defined by y^2 = x^3 + 27*x + 41 over Finite Field in img of size 71^2, (19*img + 2 : 37*img + 67 : 1), (57*img + 11 : 4*img + 51 : 1)) PKB: (Elliptic Curve defined by y^2 = x^3 + 13*x + 66 over Finite Field in img of size 71^2, (23*img + 44 : 32*img + 7 : 1), (46*img + 50 : 22*img + 43 : 1)) """
6.在完成上述的步骤后,A使用B的公钥 $E_B,\phi_B(P_A),\phi_B(Q_A)$ 和自己的私钥 $x_A$,计算 $S_{AB}=\phi_B(P_A)+x_A\phi_B(Q_A)$,然后走和之前相同的步骤。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Eab=phiB.codomain() Pab,Qab=phiB(Pa),phiB(Qa) Sab=Pab+xa*Qabprint (Sab.xy()) Sab1=Sab Eab1=Eab Pabs,Eabs=[],[Eab]for i in range (ea-1 ,0 ,-1 ): Tab=Sab1*(2 **i) phi = Eab1.isogeny(Tab) Eabi = phi.codomain() Sab1 = phi(Sab1) Eab1=Eabi Pabs.append(phi) Eabs.append(Eabi) phiAB=Pabs[-1 ]for i in range (len (Pabs)-2 ,-1 ,-1 ): phiAB*=Pabs[i]print (phiAB)for i in range (len (Eabs)): print (Eabs[i].j_invariant(),end=' -> ' if i!=len (Eabs)-1 else '\n' )""" Output: (26*img + 40, 3*img + 35) Composite morphism of degree 4 = 2^2: From: Elliptic Curve defined by y^2 = x^3 + 13*x + 66 over Finite Field in img of size 71^2 To: Elliptic Curve defined by y^2 = x^3 + 14*x + 56 over Finite Field in img of size 71^2 66 -> 48 -> 40 """
7.同理,B使用A的公钥 $E_A,\phi_A(P_B),\phi_A(Q_B)$ 和自己的私钥 $x_B$,计算 $S_{BA}=\phi_A(P_B)+x_B\phi_A(Q_B)$,然后走和之前相同的步骤。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 Eba=phiA.codomain() Pba,Qba=phiA(Pb),phiA(Qb) Sba=Pba+xb*Qbaprint (Sba.xy()) Sba1=Sba Eba1=Eba Pbas,Ebas=[],[Eba]for i in range (eb-1 ,0 ,-1 ): Tba=Sba1*(3 **i) phi = Eba1.isogeny(Tba) Ebai = phi.codomain() Sba1 = phi(Sba1) Eba1=Ebai Pbas.append(phi) Ebas.append(Ebai) phiBA=Pbas[-1 ]for i in range (len (Pbas)-2 ,-1 ,-1 ): phiBA*=Pbas[i]print (phiBA)for i in range (len (Ebas)): print (Ebas[i].j_invariant(),end=' -> ' if i!=len (Ebas)-1 else '\n' )""" Output: (23, 7) Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 27*x + 41 over Finite Field in img of size 71^2 to Elliptic Curve defined by y^2 = x^3 + 14*x + 56 over Finite Field in img of size 71^2 17 -> 40 """
8.最终,A在计算时,得到的曲线的j-不变量的变化过程为:$66,48,40$,而B得到的曲线的j-不变量变化过程为 $17,40$。因此,双方共享的秘密值为 $40$。
2.2 代码实现 重构一下前面的代码:
2.2.1 Init 1 2 3 4 5 from random import * alph,beta=8 ,5 p=2 **alph*3 **beta-1 Cp.<img>=GF(p**2 ,modulus=[1 ,0 ,1 ]) E=EllipticCurve(Cp,[1 ,0 ])
2.2.2 ParamGen 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 def paramGen (Ec,K,eK,e5K ): assert K in [2 ,3 ] P=Ec(0 ) J=5 -K while (K**(eK-1 )*P==Ec(0 )): P=(J**e5K)*Ec.random_element() Q=Ec(0 ) while (P.weil_pairing(Q,K**eK)**(K**(eK-1 ))==1 ): Q=(J**e5K)*Ec.random_element() return P,Q Pa,Qa=paramGen(E,2 ,alph,beta)print ('Pa =' ,Pa.xy())print ('Qa =' ,Qa.xy()) Pb,Qb=paramGen(E,3 ,beta,alph)print ('Pb =' ,Pb.xy())print ('Qb =' ,Qb.xy())""" Pa = (39380*i + 3466, 17196*i + 12226) Qa = (16683*i + 35698, 11691*i + 44683) Pb = (32011*i + 53204, 48668*i + 25851) Qb = (3742*i + 40029, 60467*i + 51431) """
2.2.3 KeyGen 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 def pkGen (P,Q,Po,Qo,x,Ec ): S = P+x*Q phi = Ec.isogeny(S,algorithm="factored" ) E1 = phi.codomain() return E1,phi(Po),phi(Qo) xa=randint(2 ,2 **alph-1 ) xb=randint(2 ,3 **beta-1 )print ('xa =' ,xa)print ('xb =' ,xb) Ea,Ga,Ha = pkGen(Pa,Qa,Pb,Qb,xa,E) Eb,Gb,Hb = pkGen(Pb,Qb,Pa,Qa,xb,E)print (f'Ea : {Ea} ' )print (f'Ga = {Ga.xy()} \nHa = {Ha.xy()} ' )print (f'Eb : {Eb} ' )print (f'Gb = {Gb.xy()} \nHb = {Hb.xy()} ' )""" xa = 72 xb = 174 Ea : Elliptic Curve defined by y^2 = x^3 + (10061*i+1875)*x + (44734*i+35632) over Finite Field in i of size 62207^2 Ga = (2283*i + 47170, 34825*i + 48025) Ha = (40463*i + 37692, 51159*i + 38421) Eb : Elliptic Curve defined by y^2 = x^3 + (49242*i+18182)*x + (7897*i+49589) over Finite Field in i of size 62207^2 Gb = (27311*i + 57671, 21378*i + 7288) Hb = (31852*i + 50453, 6044*i + 46259) """
2.2.4 + Key Exchange 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def getSecret (Ec,P,Q,x ): Key = P+x*Q phi = Ec.isogeny(Key,algorithm="factored" ) return phi.codomain().j_invariant() Keya = getSecret(Eb,Gb,Hb,xa)print ('Keya =' ,Keya) Keyb = getSecret(Ea,Ga,Ha,xb)print ('Keyb =' ,Keyb)assert Keya==Keyb""" Keya = 10325*i + 49607 Keyb = 10325*i + 49607 Assert Pass. """
2.3 SIDH安全性分析 2.3.1 论文链接 & 论文附着代码 SIDH目前已经被破解了,GitHub上目前也有了很多SageMath的的代码,A 可以在只知道 B 的公钥的情况下,确定 B 的私钥。最快的方法只需要几十秒就可以攻破 400 位标准的参数。
论文链接2022-975 攻击SIDH的代码
论文中代码的运行结果:
2.3.2 06010型曲线的攻击 当然作为一个CTFer,既然人家都已经破解了SIDH了,我们当然要学会用他的代码。
可以看到,该代码中,使用的是 $y^2=x^3+6x^2+x$ 的曲线,而CTF题目中,常用的曲线是 $y^2=x^3+x$,很明显,两个曲线都是蒙哥马利曲线,但不同源,所以不存在同构映射。
在阅读论文之后,可以发现,论文的核心部分,是要构造出一个曲线上的自同态 $\phi$,满足 $\phi(\phi(P))=-4P$。这个 $\phi$ 又被记作 $\phi_{2\mathrm i}$。可以发现,这个攻击代码中的 public_values_aux.py
文件中,有这样一个函数,似乎限制死了曲线的形式为 $y^2=x^3+6x^2+x$。
1 2 3 4 def generate_distortion_map (E ): if E.a_invariants() != (0 ,6 ,0 ,1 ,0 ): raise NotImplementedError return E.isogeny(E.lift_x(ZZ(1 )), codomain=E)
而阅读其攻击代码SIKEp434.sage
,可以发现这样一行,恰好是为了求 $\phi_{2\mathrm i}$ 用的
1 two_i = generate_distortion_map(E_start)
经过测试也的确如此:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def generate_distortion_map (E ): if E.a_invariants() != (0 ,6 ,0 ,1 ,0 ): raise NotImplementedError return E.isogeny(E.lift_x(1 ), codomain=E) p=2 **8 *3 **5 -1 F.<i>=GF((p,2 ),modulus=[1 ,0 ,1 ]) E1=EllipticCurve(F,[0 ,6 ,0 ,1 ,0 ]) G=E1.random_element() phi=generate_distortion_map(E1)print (G.xy())print ((-4 *G).xy())print (phi(phi(G)).xy()) (54868 *i + 58756 , 51614 *i + 43751 ) (32804 *i + 60579 , 20634 *i + 8371 ) (32804 *i + 60579 , 20634 *i + 8371 )
因此,只要我们搞出了 $\phi_{2\mathrm i}$,那么我们就可以直接使用其代码了。我们可以先从Git上下载这个代码的zip,解压到某个文件夹中,然后写入这样的测试代码(答案是 $248011$):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 import public_values_auxfrom public_values_aux import * load('castryck_decru_shortcut.sage' ) a, b = 18 ,13 p = 2 ^a*3 ^b - 1 public_values_aux.p = p Fp2.<i> = GF(p^2 , modulus=x^2 +1 ) R.<x> = PolynomialRing(Fp2) E_start = EllipticCurve(Fp2, [0 ,6 ,0 ,1 ,0 ]) E_start.set_order((p+1 )^2 , num_checks=0 ) two_i = generate_distortion_map(E_start) P2=E_start(220737745801 *i + 50222311055 , 190367540881 *i + 54017057412 ) Q2=E_start(140405500965 *i + 258042847301 , 297210225013 *i + 344888892331 ) P3=E_start(354749614347 *i + 280322752628 , 85255872295 *i + 255093011257 ) Q3=E_start(187154306904 *i + 79900133137 , 220502934600 *i + 334923255776 ) check_torsion_points(E_start, a, b, P2, Q2, P3, Q3) a2=6 a4=(227348106349 *i+257259789242 ) a6=(4035550462 *i+119078416285 ) EB=EllipticCurve(Fp2,[0 ,a2,0 ,a4,a6]) PB=EB(91970188975 *i + 124693845086 , 377253313719 *i + 322377957916 ) QB=EB(198072574684 *i + 400866480110 , 96532007619 *i + 380763487262 ) recovered_key = CastryckDecruAttack(E_start, P2, Q2, EB, PB, QB, two_i, num_cores=1 )print (recovered_key)
运行结果如下:
换一组参数试试,这次答案是 $53361602935692906567490749144731$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 import public_values_auxfrom public_values_aux import * load('castryck_decru_shortcut.sage' ) a, b = 110 ,67 p = 2 ^a*3 ^b - 1 public_values_aux.p = p Fp2.<i> = GF(p^2 , modulus=x^2 +1 ) R.<x> = PolynomialRing(Fp2) E_start = EllipticCurve(Fp2, [0 ,6 ,0 ,1 ,0 ]) E_start.set_order((p+1 )^2 , num_checks=0 ) two_i = generate_distortion_map(E_start) P2=E_start(56610319193701558658735766617880355615385547932040925880687156764 *i + 42698419292581064688242589979397467965126090170436941878853866568 , 35736771060022153096871481140526466092251776000496542458805572451 *i + 1406713305674803984210143602460748242038256281655932542401586960 ) Q2=E_start(87385346712865167405378671004116905429368722879634257587922373265 *i + 20868980497449673695168909270503567045204488768234841927361424254 , 93809470233601384687277542711720615096979514120814893736747406702 *i + 102071080287673632345798509543832980678489137189256701006149797955 ) P3=E_start(108340825021242044737371303329468146504320017600004306920882246903 *i + 108396170192786465171102545295777043093136519196500623859843999594 , 39510198811668974327487043561554886437520251439351004986533313590 *i + 98384580631758549086105854565205076233552192646375463524786202427 ) Q3=E_start(117708790334138506086639601581650847896208982849168647458602305949 *i + 60171539076219076100859521953631698080351790640949638221590204795 , 108234927295372521953904890581286233187456939597045817923583613193 *i + 17111981949141181871590974861722205288395470270406688160159342438 ) check_torsion_points(E_start, a, b, P2, Q2, P3, Q3) a2=6 a4=(33352492415821181878007294686911877407020167370184992026961189883 *i+360155498372969691801778829113065642920064704754943849117579719 ) a6=(71078007951164850613906284431026209801045803425464743236950552863 *i+60050844645541971863484821267140778695102640789034683181783646104 ) EB=EllipticCurve(Fp2,[0 ,a2,0 ,a4,a6]) PB=EB(44655967089538875652566632875838189177891417754246765262862174361 *i + 95761508234935577002311855392466107543835007665570312539644748521 , 85321383142345971885193090537643266036849312093691332425107553101 *i + 113017953225856300262660175780097470661672131417143141502018264468 ) QB=EB (71214736694275496825585051349583527644008441002295381958581065547 *i + 118100008118642712698371498755385508818364986084944574352354913594 , 54703329181345516353291579273842096570542601384268943693078600755 *i + 84401862403085750806051707190053760164677853749560631699068036990 ) recovered_key = CastryckDecruAttack(E_start, P2, Q2, EB, PB, QB, two_i, num_cores=1 )print (recovered_key)
可以看到,得到的结果也很快
当然,也可以使用2.2节的代码进行测试。其中: E_start
为原始曲线,$P_2,Q_2,P_3,Q_3$ 对应2.2节代码中的 $P_A,Q_A,P_B,Q_B$,而这个代码中的 $E_B,P_B,Q_B$ 对应2.2节代码中的 $E_B,G_B,H_B$。
2.3.3 00010型曲线的攻击 在论文的第 5 章,我们得到了这样的内容,虽然翻译是机器翻译,但可以看到 $\phi_{2\mathrm i}$ 的映射表达式为: $$ \phi_{2\mathrm i}: E(x,y)\rightarrow 2 E(-x,\mathrm iy) $$
因此,对于曲线 $y^2=x^3+x$,上面的 two_i
可以这样写:
1 2 3 4 5 6 7 8 9 10 def two_i (Point ): Ec=Point.curve() if (Point==Ec(0 )): return Ec(0 ) else : xx,yy=Point[0 ],Point[1 ] xx=-xx yy=i*yy iPoint=Ec(xx,yy) return 2 *iPoint
那么我们也可以得到攻击代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 import public_values_auxfrom public_values_aux import * load('castryck_decru_shortcut.sage' ) a, b = 110 ,67 p = 2 ^a*3 ^b - 1 public_values_aux.p = p Fp2.<i> = GF(p^2 , modulus=x^2 +1 ) R.<x> = PolynomialRing(Fp2) E_start = EllipticCurve(Fp2, [0 ,0 ,0 ,1 ,0 ]) E_start.set_order((p+1 )^2 , num_checks=0 ) def two_i (Point ): Ec=Point.curve() if (Point==Ec(0 )): return Ec(0 ) else : xx,yy=Point[0 ],Point[1 ] xx=-xx yy=i*yy iPoint=Ec(xx,yy) return 2 *iPoint P2=E_start(17195814840046408112963036169949156976799365698953771024820414396 *i + 102931389186229048337379830319785276552723380376115687557503025718 , 75778504057793479951018813267308472337220743929059667604796986592 *i + 47914122352720119988527881631858648853952573354238926350337613260 ) Q2=E_start(54540319919150579200374436040602436895070957026612529299060696661 *i + 64225985661603535357333706579836161964656161457361578265449177285 , 2267083341011364099622517802559653254244413235641444399445423098 *i + 23770653458973066207606115403897464007836542603675434759121428748 ) P3=E_start(7989847351628672981078106697557859098767196162395305639242023745 *i + 89231383320582491381266348351541796604215452931393417057299686215 , 99238707995304975968036268582514064981961075071032579111594311603 *i + 38199292319769952631065248630069261885287525329034800830358661747 ) Q3=E_start(4663695293244872101098475353375523205838970445774326103489210382 *i + 32961768669728583913855961871446561181466638649804077352262661465 , 52712260135577782637658195833849499206999684173146994531696493355 *i + 90137853988314928573189276753486360557512526456632678305271362467 ) check_torsion_points(E_start, a, b, P2, Q2, P3, Q3) a2=0 a4=(102418828187774457761879456577153513507915057359277718737712550111 *i+31532950820601891722920142855587562494984182810592253153908855275 ) a6=(81186662414448050665979201453065315156725879839182514894602516221 *i+114855290460797749422119777020804067441781626139255389813090673539 ) EB=EllipticCurve(Fp2,[0 ,a2,0 ,a4,a6]) PB=EB(41424643566869521367632949668986202694950053240719386036239671784 *i + 97100535686874659598560862233789138506102606757930590165770050211 , 28478553207476926857405639847764592248944426695136614829558619038 *i + 57112427683516687662270959498666544806334396087049034869773482261 ) QB=EB(83903916904730001170172551063303069216164579013051205895824540388 *i + 94290363880834426978339452165347196781962782250248107794345225206 , 89180000462470351871791116928719101870428228473355925736419881028 *i + 95407185118153375790239945730336656643579227622240889452855365824 ) recovered_key = CastryckDecruAttack(E_start, P2, Q2, EB, PB, QB, two_i, num_cores=1 )print (recovered_key)
运行结果如下:
2.9 总结与回顾 CryptoHack的SIDH部分
2.9.1 同源曲线的求法 2同源 1 2 3 4 5 p=2 **18 *3 **13 -1 F.<img>=GF((p,2 ),modulus=[1 ,0 ,1 ]) E=EllipticCurve(F,[1 ,0 ]) P=E(img,0 ) E.isogeny(P).codomain().j_invariant()
3同源 1 2 3 4 5 p=2 **18 *3 **13 -1 F.<img>=GF((p,2 ),modulus=[1 ,0 ,1 ]) E=EllipticCurve(F,[1 ,0 ]) P=E(483728976 ,174842350631 ) E.isogeny(P).codomain().j_invariant()
混合同源 需要注意的是,混合同源必须加 algorithm='factored'
,否则会非常慢,并且内存还会被卡爆。。。
1 2 3 4 5 p=2 **18 *3 **13 -1 F.<i>=GF((p,2 ),modulus=[1 ,0 ,1 ]) E=EllipticCurve(F,[1 ,0 ]) P=E(357834818388 *i+53943911829 ,46334220304 *i+267017462655 )print (E.isogeny(P,algorithm='factored' ).codomain().j_invariant())
2.9.2 SIDH的应用 这个题目提示了SIDH的实际应用
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 import osfrom Crypto.Cipher import AESfrom Crypto.Hash import SHA256from Crypto.Util.Padding import pad FLAG = b"crypto{?????????????????????????????????????}" ea, eb = 110 , 67 p = 2 **ea*3 **eb - 1 F.<i> = GF(p**2 , modulus=[1 ,0 ,1 ]) E0 = EllipticCurve(F, [1 ,0 ]) P2 = E0(118242575052254473701407051403380184157502700009529430046122822477 *i + 57638278144985143549644316704182130279784191379170896458696787312 , 80915735815367072410310689908590367651933218830435520913424043510 *i + 35228327576503752484578273317308597612913304063200715424014549037 ) Q2 = E0(27856673727210297071672501895829918842041821446996051944738115273 *i + 101349537690838191347553037323956940169953967852439843389873653018 , 45955772915614774101614751673022340983778200451506382887743008335 *i + 76499786039494489791183573966490259392789635716963920208794989512 ) P3 = E0(68702305424425607424554396971378391833152415806389206440833676844 *i + 63162905189208938201083385603424075109355856156240516441321158383 , 14452401602439328239712793251073780692192036710425129093829067649 *i + 110903430163815016394569999096524527007769669322432532390635606190 ) Q3 = E0(50967992419888058158544483269655763559879646024537212566396940681 *i + 39165103284419354968504615023980382940222714919046676966425620242 , 113476160032430656302485251779124302915433268423829474022852380544 *i + 74814862075401178218909769629701747112662266906635780085603780902 ) sA = 225902606209514408534212339057054 sB = 38410379124791756271891302485727 def gen_public_key (): pass def gen_shared_secret (): pass shared_secret = gen_shared_secret()def encrypt_flag (shared_secret ): key = SHA256.new(data=str (shared_secret).encode()).digest()[:128 ] iv = os.urandom(16 ) cipher = AES.new(key, AES.MODE_CBC, iv) ct = cipher.encrypt(pad(FLAG, 16 )) return iv.hex (), ct.hex ()print (encrypt_flag(shared_secret))
既然参数全都给出了,那后面就是走流程了!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 from random import * alph,beta=110 ,67 p=2 **alph*3 **beta-1 Cp.<i>=GF(p**2 ,modulus=[1 ,0 ,1 ]) E=EllipticCurve(Cp,[1 ,0 ]) Pa = E(118242575052254473701407051403380184157502700009529430046122822477 *i + 57638278144985143549644316704182130279784191379170896458696787312 , 80915735815367072410310689908590367651933218830435520913424043510 *i + 35228327576503752484578273317308597612913304063200715424014549037 ) Qa = E(27856673727210297071672501895829918842041821446996051944738115273 *i + 101349537690838191347553037323956940169953967852439843389873653018 , 45955772915614774101614751673022340983778200451506382887743008335 *i + 76499786039494489791183573966490259392789635716963920208794989512 ) Pb = E(68702305424425607424554396971378391833152415806389206440833676844 *i + 63162905189208938201083385603424075109355856156240516441321158383 , 14452401602439328239712793251073780692192036710425129093829067649 *i + 110903430163815016394569999096524527007769669322432532390635606190 ) Qb = E(50967992419888058158544483269655763559879646024537212566396940681 *i + 39165103284419354968504615023980382940222714919046676966425620242 , 113476160032430656302485251779124302915433268423829474022852380544 *i + 74814862075401178218909769629701747112662266906635780085603780902 )def pkGen (P,Q,Po,Qo,x,Ec ): S = P+x*Q phi = Ec.isogeny(S,algorithm="factored" ) E1 = phi.codomain() return E1,phi(Po),phi(Qo)def getSecret (Ec,P,Q,x ): Key = P+x*Q phi = Ec.isogeny(Key,algorithm="factored" ) return phi.codomain().j_invariant() xa = 225902606209514408534212339057054 xb = 38410379124791756271891302485727 print ('xa =' ,xa)print ('xb =' ,xb) Ea,Ga,Ha = pkGen(Pa,Qa,Pb,Qb,xa,E) Eb,Gb,Hb = pkGen(Pb,Qb,Pa,Qa,xb,E)print (f'Ea : {Ea} ' )print (f'Ga = {Ga.xy()} \nHa = {Ha.xy()} ' )print (f'Eb : {Eb} ' )print (f'Gb = {Gb.xy()} \nHb = {Hb.xy()} ' ) Keya = getSecret(Eb,Gb,Hb,xa)print ('Keya =' ,Keya) Keyb = getSecret(Ea,Ga,Ha,xb)print ('Keyb =' ,Keyb)assert Keya==Keybfrom hashlib import sha256from Crypto.Cipher import AES key = sha256(str (Keyb).encode()).digest() iv = bytes .fromhex('05a4cfbce59acb952128af83c9694390' ) ct = bytes .fromhex('755b72b2e3bef2e7a4b2ce4a370f287ad04c1359bace25f3def8be23c0c49e89b4302408ad2dcb02d4875fe58c543d91' )print (AES.new(key, AES.MODE_CBC, iv).decrypt(ct))
2.9.3 SIDH的破解 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 import osfrom Crypto.Cipher import AESfrom Crypto.Hash import SHA256from Crypto.Util.Padding import pad FLAG = b"crypto{??????????????????????????????????}" f, ea, eb = 45 , 117 , 73 p = f * 2 **ea * 3 **eb - 1 F.<i> = GF(p**2 , modulus=[1 ,0 ,1 ]) E0 = EllipticCurve(F, [1 ,0 ]) P2 = E0(41638913017947770142057706586022928767376787911881052119498505735726709 *i + 42302691118463190267789836743381974415789982933013793177648925959412830 , 398449090103547450120756760379594152224190852334260435573814509309180322 *i + 233727912055570344238170576715487571464638389819881232356163774868717298 ) Q2 = E0(206871044564057174074702402057560500385307897843892757429570895488690781 *i + 345361103047041832006854423588672657209780675425156486637093636756615871 , 282631959619596644195862856762358013067369927756734494353761273142886198 *i + 424042212353240809393676298236811630816767068488333281198829926787994817 ) P3 = E0(283521037412897973446265653799790187322986891540188206463957119516634991 *i + 54836870836833212880150277757892094716552831163383470059384919428256731 , 161092808075362244162644980545740896186924081971711047761724742595133944 *i + 197849415496275495990937264988931290383245818223505983906164366276638868 ) Q3 = E0(170277682213687313511268961329652085176588846737029816748389863411297316 *i + 110089263347312130053961094497783417490346085079501067635398757092208463 , 198706722901789469217115416185417389094489501048971022152415817993951671 *i + 257742376830499988002294097301881965831489887177374506301544311076566391 ) EAa = 341962904043010047547037514847227313183414494665183661406956171643838238 *i+466221816892334489710400228219157166377700467211697103422573316531708902 EAb = 145050307288456998377054421680667611887270583594997309677606837459597101 *i+356616269078165763297060128562598654455817286639025312561154777133108454 EA = EllipticCurve(F, [EAa, EAb]) phiA_P3 = EA(180748165080544728482273627011017446820851964671689844940751613607027042 *i + 386399657558539814871631131488087670882259175999167407491042206165954470 , 327787397151786462956783797299341040567085054575313609836298710436619785 *i + 196105866987178697015232911678783180764030519956520455354300809913687633 ) phiA_Q3 = EA(258847568494100760477286708131798122974987254057932346978697593107825530 *i + 38490496870779580975180675248455270468746617165569920252532162902409675 , 306358844762893197793766376830898073944594560219460755063030400129179690 *i + 182510704835708623157232097040016637690000728438765134566515343181898854 ) EBa = 157597846018840576315827348546173953758796122446152006870494733059078284 *i+418874181143594794621438950780746815165757267567012420151805770819363162 EBb = 348442605611456141157838566652599367279127166743233127676107176086957458 *i+420861724499942691978671729713269838482830342041809365231340529697579831 EB = EllipticCurve(F, [EBa, EBb]) phiB_P2 = EB(109886154562978369974676578144987934657805602134271866282447816334164466 *i + 498136804583811803693793430218572265900633458962105597996566642692906940 , 401907510168736586072062757459383110335655309941214043767511647670013113 *i + 259294509134396545471598619471155420455160713238944617603235341590681170 ) phiB_Q2 = EB(273276717406517362983403161180051140354308241184578465602742126078679674 *i + 164406415263418135648467271613257338667532330432266713670747057596335763 , 1092247214699018416365584399170122624205811861075813640384878660598131 *i + 354817717070268141803451242665805576947926358877574336158195333352961708 )def encrypt_flag (shared_secret ): key = SHA256.new(data=str (shared_secret).encode()).digest()[:128 ] iv = os.urandom(16 ) cipher = AES.new(key, AES.MODE_CBC, iv) ct = cipher.encrypt(pad(FLAG, 16 )) return iv.hex (), ct.hex () iv = 'f45273daf12b8234bd41607d8b517913' ct = '65917ae4d3de3ba753d50bab78992b2239cb189493807fcc3da8d058da1eda7d993c041d0ecb09089808d759a982f087'
这个题给了SIDH的公共参数,但私钥未知,我们的目标是求出最终能双方共享的秘密值。直接一把梭了:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 import public_values_auxfrom public_values_aux import * load('castryck_decru_shortcut.sage' ) a, b = 117 ,73 p = 45 *2 ^a*3 ^b - 1 public_values_aux.p = p Fp2.<i> = GF(p^2 , modulus=x^2 +1 ) R.<x> = PolynomialRing(Fp2) E_start = EllipticCurve(Fp2, [0 ,0 ,0 ,1 ,0 ]) E_start.set_order((p+1 )^2 , num_checks=0 ) def two_i (Point ): Ec=Point.curve() if (Point==Ec(0 )): return Ec(0 ) else : xx,yy=Point[0 ],Point[1 ] xx=-xx yy=i*yy iPoint=Ec(xx,yy) return 2 *iPoint E0=E_start P2 = E0(41638913017947770142057706586022928767376787911881052119498505735726709 *i + 42302691118463190267789836743381974415789982933013793177648925959412830 , 398449090103547450120756760379594152224190852334260435573814509309180322 *i + 233727912055570344238170576715487571464638389819881232356163774868717298 ) Q2 = E0(206871044564057174074702402057560500385307897843892757429570895488690781 *i + 345361103047041832006854423588672657209780675425156486637093636756615871 , 282631959619596644195862856762358013067369927756734494353761273142886198 *i + 424042212353240809393676298236811630816767068488333281198829926787994817 ) P3 = E0(283521037412897973446265653799790187322986891540188206463957119516634991 *i + 54836870836833212880150277757892094716552831163383470059384919428256731 , 161092808075362244162644980545740896186924081971711047761724742595133944 *i + 197849415496275495990937264988931290383245818223505983906164366276638868 ) Q3 = E0(170277682213687313511268961329652085176588846737029816748389863411297316 *i + 110089263347312130053961094497783417490346085079501067635398757092208463 , 198706722901789469217115416185417389094489501048971022152415817993951671 *i + 257742376830499988002294097301881965831489887177374506301544311076566391 ) check_torsion_points(E_start, a, b, P2, Q2, P3, Q3) a4 = 157597846018840576315827348546173953758796122446152006870494733059078284 *i+418874181143594794621438950780746815165757267567012420151805770819363162 a6 = 348442605611456141157838566652599367279127166743233127676107176086957458 *i+420861724499942691978671729713269838482830342041809365231340529697579831 EB = EllipticCurve(Fp2, [a4, a6]) PB = EB(109886154562978369974676578144987934657805602134271866282447816334164466 *i + 498136804583811803693793430218572265900633458962105597996566642692906940 , 401907510168736586072062757459383110335655309941214043767511647670013113 *i + 259294509134396545471598619471155420455160713238944617603235341590681170 ) QB = EB(273276717406517362983403161180051140354308241184578465602742126078679674 *i + 164406415263418135648467271613257338667532330432266713670747057596335763 , 1092247214699018416365584399170122624205811861075813640384878660598131 *i + 354817717070268141803451242665805576947926358877574336158195333352961708 ) recovered_key = CastryckDecruAttack(E0, P2, Q2, EB, PB, QB, two_i, num_cores=1 )print (recovered_key)
拿到私钥后,就很简单了,走流程就OK:)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 from random import * alph,beta=117 ,73 p=45 *2 **alph*3 **beta-1 F.<i>=GF(p**2 ,modulus=[1 ,0 ,1 ]) E0=EllipticCurve(F,[0 ,0 ,0 ,1 ,0 ]) Pa = E0(41638913017947770142057706586022928767376787911881052119498505735726709 *i + 42302691118463190267789836743381974415789982933013793177648925959412830 , 398449090103547450120756760379594152224190852334260435573814509309180322 *i + 233727912055570344238170576715487571464638389819881232356163774868717298 ) Qa = E0(206871044564057174074702402057560500385307897843892757429570895488690781 *i + 345361103047041832006854423588672657209780675425156486637093636756615871 , 282631959619596644195862856762358013067369927756734494353761273142886198 *i + 424042212353240809393676298236811630816767068488333281198829926787994817 ) Pb = E0(283521037412897973446265653799790187322986891540188206463957119516634991 *i + 54836870836833212880150277757892094716552831163383470059384919428256731 , 161092808075362244162644980545740896186924081971711047761724742595133944 *i + 197849415496275495990937264988931290383245818223505983906164366276638868 ) Qb = E0(170277682213687313511268961329652085176588846737029816748389863411297316 *i + 110089263347312130053961094497783417490346085079501067635398757092208463 , 198706722901789469217115416185417389094489501048971022152415817993951671 *i + 257742376830499988002294097301881965831489887177374506301544311076566391 ) EAa = 341962904043010047547037514847227313183414494665183661406956171643838238 *i+466221816892334489710400228219157166377700467211697103422573316531708902 EAb = 145050307288456998377054421680667611887270583594997309677606837459597101 *i+356616269078165763297060128562598654455817286639025312561154777133108454 Ea = EllipticCurve(F, [EAa, EAb]) Ga = Ea(180748165080544728482273627011017446820851964671689844940751613607027042 *i + 386399657558539814871631131488087670882259175999167407491042206165954470 , 327787397151786462956783797299341040567085054575313609836298710436619785 *i + 196105866987178697015232911678783180764030519956520455354300809913687633 ) Ha = Ea(258847568494100760477286708131798122974987254057932346978697593107825530 *i + 38490496870779580975180675248455270468746617165569920252532162902409675 , 306358844762893197793766376830898073944594560219460755063030400129179690 *i + 182510704835708623157232097040016637690000728438765134566515343181898854 ) EBa = 157597846018840576315827348546173953758796122446152006870494733059078284 *i+418874181143594794621438950780746815165757267567012420151805770819363162 EBb = 348442605611456141157838566652599367279127166743233127676107176086957458 *i+420861724499942691978671729713269838482830342041809365231340529697579831 Eb = EllipticCurve(F, [EBa, EBb]) Gb = Eb(109886154562978369974676578144987934657805602134271866282447816334164466 *i + 498136804583811803693793430218572265900633458962105597996566642692906940 , 401907510168736586072062757459383110335655309941214043767511647670013113 *i + 259294509134396545471598619471155420455160713238944617603235341590681170 ) Hb = Eb(273276717406517362983403161180051140354308241184578465602742126078679674 *i + 164406415263418135648467271613257338667532330432266713670747057596335763 , 1092247214699018416365584399170122624205811861075813640384878660598131 *i + 354817717070268141803451242665805576947926358877574336158195333352961708 ) xb=39990433064274301814750584859416466 def getSecret (Ec,P,Q,x ): Key = P+x*Q phi = Ec.isogeny(Key,algorithm="factored" ) return phi.codomain().j_invariant() Keyb = getSecret(Ea,Ga,Ha,xb)print ('Keyb =' ,Keyb)from hashlib import sha256from Crypto.Cipher import AES key = sha256(str (Keyb).encode()).digest() iv = bytes .fromhex('f45273daf12b8234bd41607d8b517913' ) ct = bytes .fromhex('65917ae4d3de3ba753d50bab78992b2239cb189493807fcc3da8d058da1eda7d993c041d0ecb09089808d759a982f087' )print (AES.new(key, AES.MODE_CBC, iv).decrypt(ct))
3.CSIDH预备知识 当然,CSIDH的预备知识还是需要的:)
REF:CSIDH 的论文 383.pdf (iacr.org)
3.1 CISDH基本思想 在SIDH中,我们使用的曲线是定义在二次扩域 $\mathbb C_p=\mathbb Z_{p}+\mathrm i\mathbb Z_{p}$ 上的超奇异椭圆曲线,其中 $p=2^\alpha3^\beta k-1$,该曲线总是有两个生成元 $P_0,Q_0$。因此通信双方可以基于 $P_0,Q_0$,选择阶为 $2^\alpha$ 和 $3^{\beta}$ 的基点 $P_A,Q_A,P_B,Q_B$ 并进行密钥交换过程。
而在CSIDH中,我们选择的是一次域 $\mathbb F_p$ 上的超奇异曲线,其中 $p+1$ 是很多小素数 $\ell_1,\ell_2,…,\ell_n$ 的乘积。设 $E$ 为所选取的曲线,由于 $E$ 的超奇异性,那么 $E$ 的阶就是 $p+1$,因此对于 $E$ 上的任意点 $P$,均存在 $\ell_1P,\ell_2P,…,\ell_nP$ ,使得 E2=E.isogeny(ell[i]*P)
存在。
很显然,既然 $E$ 是超奇异的,那么 $E_2$ 也是超奇异的,所以 $E_2$ 的阶仍然为 $p+1$,那么设 $P_2$ 是 $E_2$ 的生成元,那么还可以继续做 E3=E2.isogeny(ell[i]*P2)
,以此类推。CSIDH就是这样的思想。
3.2 同源图(蒙哥马利型) 对于一个域 $K$ 和素数 $\ell$,其中 $\ell$ 不是 $K$ 的特征($\mathrm{char} K$)的因数,那么 $K$ 有理 $\ell$ 同源图中,顶点所有在 $K$ 上定义的椭圆曲线。对于两个曲线 $E_1,E_2$ 中的每个 $K$ 有理 $\ell$ 同源,都会有一条有向边 $(E_1,E_2)$。
Sage画图代码:
1 2 3 4 5 6 7 8 9 10 E=EllipticCurve(GF(71 ),[1 ,0 ]) G=E.isogeny_ell_graph(3 ) D={'#ff9900' :[],'#00ff66' :[]}for i in G.vertices(): if (i=='y^2 = x^3 + x' ): D['#ff9900' ].append(i) else : D['#00ff66' ].append(i) plot(E.isogeny_ell_graph(3 ),vertex_labels=True ,edge_labels=True ,vertex_size=5000 ,edge_thickness=4 ,vertex_colors=D)
上面那就是一个 $\mathbb Z_{71}$ 上的度为 $3$ 同源图,我们可以看出其构成了一个循环,$y^2=x^3+47x+45$ 具有两个 $3$ 同源: $y^2=x^3+13x+66$ 和 $y^2=x^3+48$,Sage中也提供了内置函数供查询:
1 2 3 4 5 6 E=EllipticCurve(GF(71 ),[47 ,45 ]) E.isogenies_prime_degree(3 )""" [Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 47*x + 45 over Finite Field of size 71 to Elliptic Curve defined by y^2 = x^3 + 48 over Finite Field of size 71, Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 47*x + 45 over Finite Field of size 71 to Elliptic Curve defined by y^2 = x^3 + 59*x + 47 over Finite Field of size 71] """
当然,这个图有什么作用呢?很显然,根据我们现在奶所讲的内容,似乎也不太好解释。但我们可以先回顾我们之前的工作:对于一个椭圆曲线而言,我们似乎不停地在关注它的 ”j-不变量“ 和 ”蒙哥马利曲线形式“(重点是 E.montgomery_model().a2()
的值),那么我们也来写一个实验代码测一下:
1 2 3 4 5 6 7 8 9 10 11 12 13 Para=[[1 ,0 ],[13 ,66 ],[47 ,45 ],[0 ,48 ],[0 ,23 ],[47 ,26 ],[13 ,5 ]] Es=[EllipticCurve(GF(71 ),Para[i]) for i in range (7 )]for i in range (len (Es)): print (Es[i].j_invariant(),Es[i].montgomery_model().a2())""" 24 0 66 35 41 58 0 28 0 43 41 13 66 36 """
可以看出,如果我们从 $y^2=x^3+x$ 曲线对应的点为中心,会发现相互对称的两条曲线的 j-不变量相同,但蒙哥马利曲线参数却不同。并且,如果再注意看蒙哥马利曲线参数,会发现与 $y^2=x^3+x$ 节点对称的两点,其蒙哥马利曲线参数互为相反数。
3.3 二次扭曲 在代数几何的数学领域中,特征不为 $2$ 的域 $K$ 上的椭圆曲线 $E$ 具有相关的二次扭曲,即另一条椭圆曲线 $E_2$ 与 $K$ 的代数闭包上的 $E$ 同构。具体而言,椭圆曲线之间的同构是 $1$ 阶同源,即可逆同源。曲线及其扭曲具有相同的 j-不变量。(REF:维基百科)
而所谓二次扭曲,我们可以设 $d≠0$,且 $d$ 是 $p$ 的非二次剩余,那么曲线 $E:y^2=x^3+ux^2+ax+b$ 的二次扭曲的形式为 $E^d:dy^2=x^3+ux^2+ax+b$ ,或 $E^d:y^2=x^3+dux^2+d^2ax+d^3b$。因此,两条曲线上的映射满足: $$ \phi:E(x,y)\rightarrow E_2\left(\dfrac{x}{d},\dfrac{y}{d\sqrt d }\right) $$
我们来看下面的代码(E2.a_invariants()
显示 [a1,a2,a3,a4,a6]
五个值,用于简化椭圆曲线的显示):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Para=[[1 ,0 ],[13 ,66 ],[47 ,45 ],[0 ,48 ],[0 ,23 ],[47 ,26 ],[13 ,5 ]] Es=[EllipticCurve(GF(71 ),Para[i]) for i in range (7 )] E=Es[2 ]print (E.j_invariant())for i in range (4 ): E2=E.quadratic_twist() print (E2.a_invariants(),E2.montgomery_model().a2(),E2.j_invariant(),E.is_isomorphic(E2))""" 41 (0, 0, 0, 52, 59) 13 41 False (0, 0, 0, 28, 52) 13 41 False (0, 0, 0, 21, 22) 13 41 False (0, 0, 0, 23, 56) 13 41 False """ print (E.change_ring(GF(71 **2 )).is_isomorphic(E2.change_ring(GF(71 **2 ))))
可以发现,我们只说了 $d$ 是 $p$ 的二次非剩余一个条件,因此每次Sage会随机选取 $d$,但这些曲线你的蒙哥马利参数竟然全是 $13$,而我们所选取的曲线的蒙哥马利参数恰好相反!似乎就是图中关于 $y^2=x^3+x$ 节点的对称点!并且这两条曲线的j-不变量相同。但这两条曲线却不同构,难道理论出问题了吗?
那为啥叫二次扭曲呢?因为 $E$ 和 $E_2$ 在 $\mathbb F_{p^2}$ 上同构!这同时说明 j-不变量 判定同构的方法,只在二次扩域中有用!
如果对一个曲线 E
计算两次二次扭曲会怎样呢,下面的代码告诉了我们答案:我们又回到了原来的曲线中去了!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 Para=[[1 ,0 ],[13 ,66 ],[47 ,45 ],[0 ,48 ],[0 ,23 ],[47 ,26 ],[13 ,5 ]] Es=[EllipticCurve(GF(71 ),Para[i]) for i in range (7 )] E=Es[2 ]print (E.j_invariant())for i in range (4 ): E2=E.quadratic_twist().quadratic_twist() print (E2.a_invariants(),E2.montgomery_model().a2(),E2.j_invariant(),E.is_isomorphic(E2))""" 41 (0, 0, 0, 39, 16) 58 41 True (0, 0, 0, 46, 5) 58 41 True (0, 0, 0, 11, 27) 58 41 True (0, 0, 0, 62, 38) 58 41 True """
3.4 $\mathbb F_{59}$ 和 $\mathbb F_{419}$ 上的超奇异曲线 让我们再回顾一下我们刚才提到的内容:既然CSIDH是多个素数,那么我们以 $\ell_1=3,\ell_2=5$ 为例,取 $p=59$,来看看会发生什么。
Sage画图代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 >E=EllipticCurve(GF(59 ),[1 ,0 ]) >G3=E.isogeny_ell_graph(3 ) >G5=E.isogeny_ell_graph(5 ) >D={'#ff9900' :[],'#00ff66' :[]} >for i in G3.vertices():if (i=='y^2 = x^3 + x' ): D['#ff9900' ].append(i)else : D['#00ff66' ].append(i) >S3=plot(G3,title=r'3-isogeny fig on F59' ,vertex_labels=True ,edge_labels=True ,vertex_size=5000 ,edge_thickness=4 ,vertex_colors=D) >D={'#ff9900' :[],'#00ff66' :[]} >for i in G5.vertices():if (i=='y^2 = x^3 + x' ): D['#ff9900' ].append(i)else : D['#00ff66' ].append(i) >S5=plot(G5,title=r'5-isogeny fig on F59' ,vertex_labels=True ,edge_labels=True ,vertex_size=5000 ,edge_thickness=4 ,vertex_colors=D) >S=graphics_array([S3,S5]) >S.show(figsize=[12 ,12 ])
我们随后来计算一下上面所有曲线的蒙哥马利参数:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 p=59 E3s=[[1 ,0 ],[37 ,42 ],[25 ,45 ],[16 ,55 ],[0 ,2 ],[0 ,57 ],[16 ,4 ],[25 ,14 ],[37 ,17 ]] E5s=[[1 ,0 ],[0 ,30 ],[39 ,9 ],[4 ,30 ],[49 ,37 ],[49 ,22 ],[4 ,29 ],[39 ,50 ],[0 ,29 ]]for i in range (len (E3s)): E3s[i]=EllipticCurve(GF(p),E3s[i])for i in range (len (E5s)): E5s[i]=EllipticCurve(GF(p),E5s[i]) seq3,seq5=[],[]for i in range (len (E3s)): seq3.append(E3s[i].montgomery_model().a2())for i in range (len (E5s)): seq5.append(E5s[i].montgomery_model().a2())print (seq3)print (seq5)
你会发现,上下两排输出的内容似乎是相同的,只不过顺序不同,那么我们可以从节点 0 开始引线,红线是 3-同源的顺序,蓝线是 5-同源的顺序。
注1:几乎所有情况下,同源图是双向有向图,也就是 $0$ 到 $29$ 有一条边,那么 $29$ 到 $0$ 也有一条边,这里我们画成单项变,是为后面规定 正方向用的,箭头方向为同源计算的正方向,逆着箭头走为负方向。
注2:上一条也有2种不成立的情况,在这种情况下,$0$ 的出边多于入边。这2种情况为:设曲线 $E$ 在域 $K$ 上定义,此时
$E$ 的 j-不变量为 $0$ 且 $\sqrt{-3}\in K$。
$E$ 的 j-不变量为 $1728$ 且 $\sqrt{-1} \in K$。
因此,在这种限制下,模数选取需要满足要求:$p\equiv 11\pmod{12}$。
Sage 画图代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 p=59 E0=EllipticCurve(GF(p),[1 ,0 ])def get (E,x ): m = 0 res=[E.montgomery_model().a2()] while (1 ): G = choice(E(0 ).division_points(x)[1 :]) E = E.isogeny(G).codomain() if (E.montgomery_model().a2()==res[0 ]): return res else : res.append(E.montgomery_model().a2()) seq3=get(E0,3 ) seq5=get(E0,5 ) Gr = DiGraph({}, loops=True , multiedges=True , sparse=True )for i in range (len (seq3)): Gr.add_edges([(seq3[i],seq3[(i+1 )%len (seq3)],'3' )])for i in range (len (seq5)): Gr.add_edges([(seq5[i],seq5[(i+1 )%len (seq5)],'5' )]) Col={'#ff9900' :[0 ],'#00ff66' :seq3[1 :]} Dpos={}for i in range (len (seq3)): x = float (cos(pi/2 + ((2 *pi)/len (seq3))*i)) y = float (sin(pi/2 + ((2 *pi)/len (seq3))*i)) Dpos[seq3[i]]=(x,y) Gr.graphplot(edge_labels=False ,color_by_label=True ,vertex_size=500 ,vertex_colors=Col,pos=Dpos).plot()
然后也有一个 $419$ 的 图也可以参考一下,红色的线为 $3$-同源,蓝色的线为 $5$-同源,绿色的线为 $7$-同源。可以发现,$3$-同源和 $7$-同源的阶均为 $27$,而 $5$-同源的阶为 $9$。
Sage 画图代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 p=419 E0=EllipticCurve(GF(p),[1 ,0 ])def get (E,x ): m = 0 res=[E.montgomery_model().a2()] while (1 ): G = choice(E(0 ).division_points(x)[1 :]) E = E.isogeny(G).codomain() if (E.montgomery_model().a2()==res[0 ]): return res else : res.append(E.montgomery_model().a2()) seq3=get(E0,3 ) seq5=get(E0,5 ) seq52=get(EllipticCurve(GF(p),[0 ,158 ,0 ,1 ,0 ]),5 ) seq53=get(EllipticCurve(GF(p),[0 ,261 ,0 ,1 ,0 ]),5 ) seq7=get(E0,7 ) Gr = DiGraph({}, loops=True , multiedges=True , sparse=True )for i in range (len (seq3)): Gr.add_edges([(seq3[i],seq3[(i+1 )%len (seq3)],'3' )])for i in range (len (seq5)): Gr.add_edges([(seq5[i],seq5[(i+1 )%len (seq5)],'5' )]) Gr.add_edges([(seq52[i],seq52[(i+1 )%len (seq52)],'5' )]) Gr.add_edges([(seq53[i],seq53[(i+1 )%len (seq53)],'5' )])for i in range (len (seq7)): Gr.add_edges([(seq7[i],seq7[(i+1 )%len (seq7)],'7' )]) Col={'#ff9900' :[0 ],'#00ff66' :seq3[1 :]} Dpos={}for i in range (len (seq3)): x = float (cos(pi/2 + ((2 *pi)/len (seq3))*i)) y = float (sin(pi/2 + ((2 *pi)/len (seq3))*i)) Dpos[seq3[i]]=(x,y) Gr.graphplot(edge_labels=False ,color_by_label=True ,vertex_size=500 ,vertex_colors=Col,pos=Dpos).plot()
如果我们规定上图从 $0$ 引出的线中,箭头方向为正方向的话,那么密钥双方可以互相约定走法,是正着走还是反着走,那么只需要双方约定好这个参数,双方走的内容一样,那不就能够得到相同的值了吗。
3.9 总结与回顾 3.9.1 求 $p$ 同源的蒙哥马利参数 1 2 3 4 E=EllipticCurve(GF(419 ),[1 ,0 ]) G=(E(0 ).division_points(5 ))[2 ] phi=E.isogeny(G) phi.codomain().montgomery_model().a2()
3.9.2 求 $p$ 同源的阶 1 2 3 4 5 6 7 8 9 10 11 p = 419 E = EllipticCurve(GF(p), [1 , 0 ]) j = E.j_invariant() m = 0 while 1 : G = choice(E(0 ).division_points(7 )[1 :]) E = E.isogeny(G).codomain() m += 1 if E.j_invariant() == j: print (m) break
3.9.3 求不同 $p$ 同源复合的结果 1 2 3 4 5 6 7 8 9 p = 419 E = EllipticCurve(GF(p), [1 , 0 ]) ells = [3 , 5 , 7 ] key = [2 , 3 , 4 ]for ell,k in zip (ells,key): for i in range (k): G = choice(E(0 ).division_points(ell)[1 :]) E = E.isogeny_codomain(G) E.montgomery_model().a2()
3.9.4 给定曲线二次扭曲的求法 1 2 3 4 5 6 7 p = 419 E = EllipticCurve(GF(p), [1 , 0 ]) G = choice(E(0 ).division_points(3 )[1 :]) E = E.isogeny_codomain(G) E = E.quadratic_twist() E.montgomery_model().a2()
4.CSIDH算法 4.1 方案简介 4.1.1 Setup 选择素数 $p\equiv 3\pmod 8$,实际上多使用 $p=4(\prod_{i=1}^n\ell_i)-1$,其中 $\ell_i$ 是不同的小素数,以及在 $\mathbb F_p$ 上拥有自同态 $O[\sqrt {-p}]$ 上的超奇异椭圆曲线 $E:y^2=x^3+x$。这里我们选择 $p=419$,其中 $\ell=3,5,7$,$n=3$。
1 2 3 4 ells=[3 ,5 ,7 ] p=4 *prod(ells)-1 F = GF(p) E0 = EllipticCurve(F, [1 , 0 ])
4.1.2 KeyGen + KeyExchange 通信双方Alice和Bob分别生成一个 $n$ 元组 $(e_1,e_2,…,e_n)$ 作为私钥,其中 $e_i\in[-m,m]\cap \mathbb Z$。我们假设 $m=5$。
1 2 ska=[2 ,5 ,-1 ] skb=[0 ,-2 ,1 ]
随后,Alice按照 ska
的内容开始走线,Bob 按照 skb
的内容开始走线,最终双方会得到两条曲线 $E_A$ 和 $E_B$,Alice和Bob分别记录 $E_A$ 的蒙哥马利参数 $A$ 和 $E_B$ 的蒙哥马利参数 $B$,并发送给对方。
在收到对方的信息后,Alice 以 $y^2=x^3+Bx^2+x$ 为起点,Bob 以 $y^2=x^3+Ax^2+x$ 为起点,继续按照自己的参数走线,最后得到的曲线的蒙哥马利参数就是双方共享的密钥了!
在实际中,常常选取 $n=74$, $p=4(\prod_{i=1}^{74}\ell_i)-1$,其中 $\ell_1\sim\ell_{73}$ 为最小的 $73$ 个奇素数,$\ell_{74}=587$。此时 $p$ 为 $512$ 位素数,因此公钥的大小为 $64$ 字节。而私钥大小一般为 $37$ 字节,说明 $m$ 的值一般不超过 $±7$,这样才能在 $37$ 字节中塞入 $74$ 个数字。
CSIDH的代码其实非常简单,但理解起来挺难的:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def csidh (A, priv ): E = EllipticCurve(F, [0 , A, 0 , 1 , 0 ]) for sgn in [1 , -1 ]: for e, ell in zip (priv, ells): for i in range (sgn * e): while not (P := (p + 1 ) // ell * E.random_element()): pass E = E.isogeny_codomain(P) E = E.quadratic_twist() return E.montgomery_model().a2() A = csidh(0 ,ska) B = csidh(0 ,skb) key1=csidh(B,ska) key2=csidh(A,skb)print (key1,key2)
放个论文中对这部分的严谨说法
4.2 CSIDH的安全性 CSIDH是可证明量子安全的,在仅知道 $A,B$ 两个蒙哥马利参数的情况下,想要求出最终的秘密值是不可行的。其实可以看一下 $p=419$ 的那张图,秘密值相差一点,最后结果其实可以相差非常大,并且确实可以在 $m$ 很小的情况下,遍历完所有可能的取值。因此虽然SIDH被攻破了,但CSIDH目前尚未有有效的攻击方法(呃,如果这个被攻破,同源是不是就玩不起来了)。
4.3 CSIDH 例题选讲 4.3.1 CSIDHKE 这个题就是普通的CSIDH的应用,给出了公共参数,以及双方的私钥,flag用共享秘密值的sha256进行了加密。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import osfrom Crypto.Cipher import AESfrom Crypto.Hash import SHA256from Crypto.Util.Padding import pad FLAG = b"crypto{??????????????????????????????????????}" ells = [3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 , 109 , 113 , 127 , 131 , 137 , 139 , 149 , 151 , 157 , 163 , 167 , 173 , 179 , 181 , 191 , 193 , 197 , 199 , 211 , 223 , 227 , 229 , 233 , 239 , 241 , 251 , 257 , 263 , 269 , 271 , 277 , 281 , 283 , 293 , 307 , 311 , 313 , 317 , 331 , 337 , 347 , 349 , 353 , 359 , 367 , 373 , 587 ] p = 4 * prod(ells) - 1 F = GF(p) E0 = EllipticCurve(F, [1 , 0 ]) a_priv = [-1 , -2 , -3 , -3 , -2 , -3 , -3 , 0 , 2 , -1 , 2 , -1 , -2 , -3 , 1 , 2 , 1 , 2 , 0 , 0 , 1 , -1 , 0 , 2 , -1 , 0 , 0 , 0 , 1 , -1 , -3 , 1 , -1 , -3 , -3 , 2 , 2 , 1 , -1 , -1 , 1 , 0 , 1 , 1 , 1 , -2 , 2 , 2 , -2 , -2 , 0 , 0 , 2 , 0 , -1 , -3 , -2 , -2 , 0 , -1 , -3 , -1 , -2 , -3 , -2 , 2 , 1 , 1 , -2 , 0 , 1 , -1 , -3 , 2 ] b_priv = [-1 , -1 , 0 , 1 , 2 , 0 , 2 , -1 , -3 , 1 , 0 , -2 , -2 , 2 , -1 , -2 , -3 , -3 , -3 , 2 , 2 , 2 , -2 , -1 , 1 , -2 , 0 , -3 , -1 , 1 , -1 , -1 , -3 , -1 , -2 , 1 , -1 , -2 , -3 , 1 , 0 , -1 , 1 , 2 , 2 , 0 , 0 , -1 , -2 , -2 , 1 , -1 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , -3 , -2 , -1 , 2 , 0 , -3 , -2 , 1 , 1 , -2 , -1 , -1 , 2 , 0 , 1 ] shared_secret = None def encrypt_flag (shared_secret ): key = SHA256.new(data=str (shared_secret).encode()).digest()[:128 ] iv = os.urandom(16 ) cipher = AES.new(key, AES.MODE_CBC, iv) ct = cipher.encrypt(pad(FLAG, 16 )) return iv.hex (), ct.hex ()print (encrypt_flag(shared_secret))
那么直接完善CSIDH算法的整个流程就OK了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 import osfrom Crypto.Cipher import AESfrom hashlib import sha256from Crypto.Util.Padding import pad ells = [3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 , 109 , 113 , 127 , 131 , 137 , 139 , 149 , 151 , 157 , 163 , 167 , 173 , 179 , 181 , 191 , 193 , 197 , 199 , 211 , 223 , 227 , 229 , 233 , 239 , 241 , 251 , 257 , 263 , 269 , 271 , 277 , 281 , 283 , 293 , 307 , 311 , 313 , 317 , 331 , 337 , 347 , 349 , 353 , 359 , 367 , 373 , 587 ] p = 4 * prod(ells) - 1 F = GF(p) E0 = EllipticCurve(F, [1 , 0 ]) a_priv = [-1 , -2 , -3 , -3 , -2 , -3 , -3 , 0 , 2 , -1 , 2 , -1 , -2 , -3 , 1 , 2 , 1 , 2 , 0 , 0 , 1 , -1 , 0 , 2 , -1 , 0 , 0 , 0 , 1 , -1 , -3 , 1 , -1 , -3 , -3 , 2 , 2 , 1 , -1 , -1 , 1 , 0 , 1 , 1 , 1 , -2 , 2 , 2 , -2 , -2 , 0 , 0 , 2 , 0 , -1 , -3 , -2 , -2 , 0 , -1 , -3 , -1 , -2 , -3 , -2 , 2 , 1 , 1 , -2 , 0 , 1 , -1 , -3 , 2 ] b_priv = [-1 , -1 , 0 , 1 , 2 , 0 , 2 , -1 , -3 , 1 , 0 , -2 , -2 , 2 , -1 , -2 , -3 , -3 , -3 , 2 , 2 , 2 , -2 , -1 , 1 , -2 , 0 , -3 , -1 , 1 , -1 , -1 , -3 , -1 , -2 , 1 , -1 , -2 , -3 , 1 , 0 , -1 , 1 , 2 , 2 , 0 , 0 , -1 , -2 , -2 , 1 , -1 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , -3 , -2 , -1 , 2 , 0 , -3 , -2 , 1 , 1 , -2 , -1 , -1 , 2 , 0 , 1 ]def csidh (A, priv ): E = EllipticCurve(F, [0 , A, 0 , 1 , 0 ]) for sgn in [1 , -1 ]: for e, ell in zip (priv, ells): for i in range (sgn * e): while not (P := (p + 1 ) // ell * E.random_element()): pass E = E.isogeny_codomain(P) E = E.quadratic_twist() return E.montgomery_model().a2() A = csidh(0 ,a_priv) B = csidh(0 ,b_priv) key1=csidh(B,a_priv) key2=csidh(A,b_priv)assert key1==key2 iv,C= ('daf6cd181775664b099609789fb564c9' , '3dd92e255c8e677f4a92226d09f56e2b2f567052ffd4f6f60200018454a83affc2e694c2bf2ad27da38f7f49b6e89928' ) iv=bytes .fromhex(iv) C=bytes .fromhex(C) key=sha256(str (key1).encode()).digest() aes = AES.new(key, AES.MODE_CBC, iv)print (aes.decrypt(C))
4.3.2 SU_Auth 之前SUCTF出了一个SU_Auth,也是基于CSIDH的,来看一下(使用本地复现代码):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 from Crypto.Cipher import AESfrom ast import literal_evalfrom hashlib import md5import subprocess ells = [*primes(3 , 200 ), 269 ] p = 4 *prod(ells) - 1 F = GF(p) SUKEY = [randint(-3 , 3 ) for _ in range (len (ells))]def SuAuth (A, priv, LIMIT=True ): if any (priv[i] == SUKEY[i] for i in range (len (ells))) and LIMIT: return "🙅SUKEY" E = EllipticCurve(F, [0 , A, 0 , 1 , 0 ]) for sgn in [1 , -1 ]: for e, ell in zip (priv, ells): for i in range (sgn * e): while not (P := (p + 1 ) // ell * E.random_element()) or P.order() != ell: pass E = E.isogeny_codomain(P) E = E.quadratic_twist() return E.montgomery_model().a2() cipher = lambda key: AES.new(md5(key.encode()).digest(),AES.MODE_ECB) SUDOOR = cipher(str (SuAuth(0 , SUKEY, 0 ))).encrypt(b"./OPEN_THE_FLAG!" )print ("😜" , SuAuth(0 , SUKEY, 0 ))while True : AKey = SuAuth(0 , literal_eval(input ("🔑: " ))) try : subprocess.run(cipher(str (AKey)).decrypt(SUDOOR)) except : continue
我们本地测一下,会发现连上去之后,跑得非常慢,10秒才给出flag的加密值。
可以看到SUAuth中的执行过程,如果给出的KEY和SUKEY中的任何一个分量相对应,那么服务器会直接返回,不会执行后面的内容。并且程序语言执行时,一定是存在逻辑短路的,any
就相当于有一个成立久会返回。考虑到从连上到收到flag的密文用了10秒,刨去参数初始化和连接耗时,说明执行SUAuth函数至少需要 $3$ 秒以上 ,因此应该可以通过时间去判断条件成立。
由于 SUKEY 每个分量的值是 $-3$ 到 $3$,我们可以发现,发送一个全 $2$ 的Key,本地 2ms 就收到了返回结果,而发送一个全 $4$ 的Key,本地 5193ms 才给出结果,可见这个的时间差距显著,可以对SUKey进行测信道攻击爆破。
P.S. 如果考虑远程交互过程,如果两个执行时间长度超过 1 秒,那大概率是可以测信道攻击的。但据说之前强网杯那个多项式题不太行,因为时间相差太短了,虽然本地跑是6ms和50ms,但由于网络延迟的存在,这个几十毫秒还是可以忽略的
测试代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 from pwn import *from sage.all import *from datetime import * context.log_level = 'debug' ells = [*primes(3 , 200 ), 269 ] p = 4 *prod(ells) - 1 F = GF(p) n=len (ells) sh=process(['sage' ,'task11.sage' ]) ts=datetime.now() C=int (sh.recvline()[4 :].strip())print (datetime.now()-ts)print (C) sh.recvuntil(b':' ) ts=datetime.now() sh.sendline(f'{[2 ]*n} ' .encode()) sh.recvuntil(b':' )print (datetime.now()-ts) ts=datetime.now() sh.sendline(f'{[4 ]*n} ' .encode()) sh.recvuntil(b':' )print (datetime.now()-ts) sh.interactive()
那么既然知道了这个,就可以开始爆破了,以下是爆破代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 from pwn import *from sage.all import *from datetime import * context.log_level = 'debug' ells = [*primes(3 , 200 ), 269 ] p = 4 *prod(ells) - 1 F = GF(p) n=len (ells) sh=process(['sage' ,'task11.sage' ]) ts=datetime.now() C=int (sh.recvline()[4 :].strip())print (datetime.now()-ts)print (C)def attack (ind,x ): L=[x if (i==ind) else 4 for i in range (n)] sh.sendline(str (L).encode()) K=[9 ]*n sh.recvuntil(b':' )for i in (range (n)): for j in range (-3 ,4 ): stime=datetime.now() attack(i,j) sh.recvuntil(b':' ) timecost=(datetime.now()-stime).total_seconds() print (f'Attacking {i} ,{j} with timecost {timecost} seconds' ) if (timecost<0.95 ): K[i]=j print (f'Found Key[{i} ]={j} ' ) print (f'Now, Key is {K} ' ) break print (K)
运行过程中的结果,可以发现这个时间差距非常显著,并且是可以得到最终的Key的。
但到这一步又出问题了:我们不知道密文SUDOOR的内容,并且服务器是执行远程的程序才给出的,也就是说,我们需要构造一个KEY,使得构造的KEY和原始私钥的执行结果一样。
由于 $p+1=4\prod_{i=1}^n{\ell_i}$,因此 $\prod_{i=1}^n\ell_i$ 是一个 4-同源,其阶数为 $3$,也就是如果使用全 $1$ 私钥,也就是对于每个 $\ell_i$ 均沿着同源图在上面走一步,那么重复三次就会回到原点——也就是说,同源图点的个数一定是 $3$ 的倍数。
因此,密钥 K1=[3+i for i in K]
与密钥 K
是等价的,因此只需要将所有私钥的值加三,然后发送给服务器就OK了!。
那么最后的攻击代码也就出来了:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 from pwn import *from sage.all import *from datetime import * context.log_level = 'debug' ells = [*primes(3 , 200 ), 269 ] p = 4 *prod(ells) - 1 F = GF(p) n=len (ells) sh=process(['sage' ,'task11.sage' ]) ts=datetime.now() C=int (sh.recvline()[4 :].strip())print (datetime.now()-ts)print (C)def attack (ind,x ): L=[x if (i==ind) else 4 for i in range (n)] sh.sendline(str (L).encode()) K=[9 ]*n sh.recvuntil(b':' )for i in (range (n)): for j in range (-3 ,4 ): stime=datetime.now() attack(i,j) sh.recvuntil(b':' ) timecost=(datetime.now()-stime).total_seconds() print (f'Attacking {i} ,{j} with timecost {timecost} seconds' ) if (timecost<0.95 ): K[i]=j print (f'Found Key[{i} ]={j} ' ) print (f'Now, Key is {K} ' ) break print (K) sh.sendline(f'{[3 +i for i in K]} ' .encode()) print (sh.recvall(timeout=5 ))
本地测试的执行结果(随便写了个flag编译了,因此flag不是原始题目的flag):
4.3.3 CSIDH特殊参数的DDH问题 看一个题目:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 from Crypto.Cipher import AESfrom Crypto.Hash import SHA256from Crypto.Util.Padding import padimport jsonimport os ls = list (primes(3 , 112 )) + [139 ] p = 2 * prod(ls) - 1 max_exp = ceil((sqrt(p) ** (1 / len (ls)) - 1 ) / 2 ) Fp2 = GF(p**2 , names="w" , modulus=[3 , 0 , 1 ]) w = Fp2.gen() base = EllipticCurve(Fp2, [0 , 1 ]) SECRET = int .from_bytes(os.urandom(8 ), "big" ) FLAG = b"crypto{????????????????????????????????}" def encrypt_flag (secret ): key = SHA256.new(int .to_bytes(int (secret), 8 )).digest()[:128 ] iv = os.urandom(16 ) cipher = AES.new(key, AES.MODE_CBC, iv) ct = cipher.encrypt(pad(FLAG, 16 )) return iv.hex (), ct.hex ()def private (): return [randrange(-max_exp, max_exp + 1 ) for _ in range (len (ls))]def action (pub, priv ): E = pub es = priv[:] while any (es): E._order = (p + 1 ) ** 2 P = E.lift_x(GF(p).random_element()) s = +1 if P.xy()[1 ] in GF(p) else -1 k = prod(l for l, e in zip (ls, es) if sign(e) == s) P *= (p + 1 ) // k for i, (l, e) in enumerate (zip (ls, es)): if sign(e) != s: continue Q = k // l * P if not Q: continue Q._order = l phi = E.isogeny(Q) E, P = phi.codomain(), phi(P) es[i] -= s k //= l return Edef backdoor (priv ): b = 1 for e, m in zip (secret_marks, priv): b *= e ^ m return bdef package_challenge (EA, EB, EC ): def package_curve (E ): return { "a4" : list (map (int , E.a4())), "a6" : list (map (int , E.a6())) } return { "EA" : package_curve(EA), "EB" : package_curve(EB), "EC" : package_curve(EC) }def gen_challenge (bit ): privA = private() pubA = action(base, privA) privB = private() pubB = action(base, privB) shared = action(pubB, privA) t = backdoor(privA) * backdoor(privB) privC = private() while backdoor(privC) == t: privC = private() pubC = action(base, privC) if bit: return package_challenge(pubA, pubB, shared) else : return package_challenge(pubA, pubB, pubC) data = []for bit in ZZ(SECRET).bits(): data.append(gen_challenge(bit)) iv, ct = encrypt_flag(SECRET) output = {} output["iv" ] = iv output["ct" ] = ct output["challenge_data" ] = data with open ("output.txt" , "w" ) as f: f.write(json.dumps(output))
题目的大意很简单:给你三条曲线 $E_A,E_B$ 和 $E_C$,问你 $E_C$ 是 $E_A,E_B$ 复合同源得到的,还是仅仅是随机产生的的曲线,很明显的 DDH 问题的isogeny版本。
注意到这个起始曲线比较特殊:属于 $j(E_0)=0,\sqrt{-3}\in K$ 的特殊曲线,因此无法计算蒙哥马利参数。并且这个题分数还挺高,盲猜是个论文题。
搜了一圈isogeny DDH,可以找到这篇论文:2020-151.pdf ,论文第 5 章介绍了几个符号的计算方法,并且参考 18 给出了Github上的magma代码。
由于 $\delta$ 符号的计算比较简单,因此这里可以计算 $\delta(E_B,E_0)$ 和 $\delta(E_A,E_C)$ 是否相等,来判断 $E_C$ 是否是 $E_0$ 经过 $E_A,E_B$ 的复合同源。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 DATA= from Crypto.Cipher import AES ls = list (primes(3 , 112 )) + [139 ] p = 2 * prod(ls) - 1 max_exp = ceil((sqrt(p) ** (1 / len (ls)) - 1 ) / 2 ) Fp2 = GF(p**2 , names="w" , modulus=[3 , 0 , 1 ]) w = Fp2.gen() base = EllipticCurve(Fp2, [0 , 1 ]) iv,C=DATA["iv" ],DATA["ct" ] D=DATA["challenge_data" ]for i in range (len (D)): EA=EllipticCurve(Fp2,[D[i]['EA' ]['a4' ],D[i]['EA' ]['a6' ]]) EB=EllipticCurve(Fp2,[D[i]['EB' ]['a4' ],D[i]['EB' ]['a6' ]]) EC=EllipticCurve(Fp2,[D[i]['EC' ]['a4' ],D[i]['EC' ]['a6' ]]) D[i]=(EA,EB,EC) PR.<x>=PolynomialRing(GF(p))def comp (E1,E2 ): f=PR([E1.a6(),E1.a4(),0 ,1 ]) g=PR([E2.a6(),E2.a4(),0 ,1 ]) r=f.roots()[0 ][0 ] s=g.roots()[0 ][0 ] judg=GF(p)((E1.a4()+3 *r**2 )/(E2.a4()+3 *s**2 )) return judg**((p-1 )//4 )==1 M=[comp(D[i][0 ],D[i][2 ])==comp(D[i][1 ],base) for i in range (len (D))] s=0 for i in range (len (M)): s+=(M[i]<<i)from Crypto.Util.number import *from hashlib import * key=sha256(long_to_bytes(s)).digest() aes=AES.new(key, AES.MODE_CBC, bytes .fromhex(iv)) aes.decrypt(bytes .fromhex(C))
9.总结 真难,好多内容感觉比4年前学LLL的时候还抽象,部分知识其实自己根本就不太懂,但为了速成一波,还是硬着头皮,通过测试代码的方式,用了一个星期(2.1到2.8),对同源有了一个基本理解了。。。等后面遇到题目再推进吧!