# Isogenies/Cryptohack
* Đây là 1 mảng mới được ứng dụng dựa trên các đường cong elliptic siêu kỳ dị. Từ đó phát triển lên các khái niệm mật mã mới là **SIDH** và **CSIDH**.
* Để nhớ lại các khái niệm liên quan tới **ECC** thì mình tham khảo [ở đây](https://hackmd.io/@nomorecaffeine/SyjQeqRZh#ELLIPTIC-CURVES-IN-CRYPTOGRAPHY)
* Do các hàm trong **sagemath** liên quan tới **Isogenies** khá mới nên mình có đọc ở [đây](https://doc.sagemath.org/html/en/reference/arithmetic_curves/sage/schemes/elliptic_curves/ell_curve_isogeny.html)
* Còn 1 số khái niệm quan trọng nữa của mảng này đó là
* **Phép đẳng cấu giữa các đường cong elliptic**:
* Nếu dựa trên lí thuyết đồ thị như trong toán rời rạc hoặc mấy phần graph trong lập trình thi đấu thì xem [ở đây](https://vi.wikipedia.org/wiki/Ph%C3%A9p_%C4%91%E1%BA%B3ng_c%E1%BA%A5u_%C4%91%E1%BB%93_th%E1%BB%8B)
* **Phép đẳng cấu (isomorphism)** giữa hai đường cong elliptic là
**một ánh xạ (hàm ánh xạ)** bảo toàn cấu trúc nhóm giữa các điểm trên hai đường cong elliptic. Xét hai đường cong elliptic $E_1,E_2$, thì định nghĩ 1 **phép đẳng cấu** là **phép song ánh (bijection)** $φ : E_1 -> E_2$ sao cho φ là một phép đồng cấu nhóm: nghĩa là với mọi điểm $𝑃,𝑄∈𝐸_1$ , ta có $𝜑(𝑃+𝑄)=𝜑(𝑃)+𝜑(𝑄)$ trong $𝐸_2$. Đây là điều kiện bảo toàn phép cộng trên các đường cong elliptic.
* Phép ánh xạ $𝜑$ phải bảo toàn điểm gốc $O$ (điểm vô cực), tức là $𝜑(𝑂_{𝐸_1})=𝑂_{𝐸_2}$ , trong đó $𝑂_{𝐸_1}$ và $0_{𝐸_2}$ là các điểm vô cực tương ứng của $𝐸_1$ và $𝐸_2$
* $𝜑$ phải là một ánh xạ đại số khả nghịch, nghĩa là tồn tại một ánh xạ $𝜑^{−1} : 𝐸_2→𝐸1$ để ánh xạ ngược lại. $𝜑^{−1}$ còn được gọi là **isogeny** đối ngẫu.
* Ví dụ:
Cho $E_1$ : $y^2 = x^3 + x + 2$
và $E_2$ : $y^2 = x^3 + 16x + 128$
Thì ta có thể tìm được 1 trong rất nhiều phép đẳng cấu thỏa mãn chẳng hạn như : $𝜑(x,y) = (4x,8y)$.
Để kiểm tra thì đơn giản bạn chỉ cần thay giá trị $x' = 4x,y' = 8y$ vào $E_1$ xem có ra 1 đường cong mới giống $E_2$ không là được. Còn phép $𝜑^{−1}(x,y) = (\frac{x}{4},\frac{y}{8})$ .
Hoặc ví dụ khác:
* Ý nghĩa: Vậy phép đẳng cấu này có tác dụng gì ? Dựa vào những gì mình tìm hiểu ở trên thì do nó bảo toàn cấu trúc nhóm giữa 2 đường cong elliptic, hay dễ hiểu hơn là nó "giống nhau" bản chất dù khác công thức . Từ đó cho ta chuyển đổi giữa các đường cong mà không làm mất đi các thuộc tính cơ bản của chúng.
* **Kernel**:
* **Kernel** của một **isogeny** giữa **hai đường cong elliptic** là **tập hợp các điểm** trên **đường cong nguồn** mà khi áp dụng isogeny, chúng **ánh xạ tới điểm vô cùng** trên **đường cong đích**.
* Ví dụ có 1 isogeny $𝜑 : E_1 → E_2$ thì $ker(𝜑)$ là tập hợp các điểm $P ∈ E_1$ sao cho $𝜑(P)=O$ với $O$ là điểm vô cực trên $E_2$.
* Kích thước của **Kernel**: Kích thước của **kernel** cho biết số lượng điểm trong tập hợp này. Nếu **kernel** có kích thước $𝑛$, điều này có nghĩa là có $n$ điểm ánh xạ tới điểm vô cùng.
* Ngắn gọn lại thì nếu **isogeny** có bậc $n$, thì $∣ker(𝜙)∣=n$
* **Degree của Isogeny**:
* **Degree** của một isogeny là **số lượng các điểm trong kernel**. Nếu isogeny có bậc **d**, điều đó có nghĩa là kích thước của **kernel** là **d**.
* Ví dụ: Khi một isogeny có bậc là 2, điều này có nghĩa là kernel chứa 2 điểm. Trong trường hợp này, kernel sẽ bao gồm điểm vô cực và một điểm khác trên đường cong.
* Túm lại : **size of a kernel = degree**
# Challenge
:::warning
Do là mảng này mình viết khá dài, mà hackmd giới hạn độ dài writeups nên mình xin phép không push source code của challenge đã cho. Các bạn đọc thì chịu khó lên [Cryptohack](https://cryptohack.org/) để xem đề nhen.
:::
## Introduction
### Introduction to Isogenies
* 
* Như mình nói ở trên thì : **size of a kernel = degree**
* **Flag: 65537**
## Starter
### The j-invariant
* 
* Ở đây họ kí hiệu $k$ là 1 trường thì $\overline{k}$ là [phần đóng đại số](https://en.wikipedia.org/wiki/Algebraic_closure) của nó.
* Thì họ bonus thêm là 2 đường cong đồng cấu trên $\overline{k}$ khi và chỉ khi nó có cùng 1 giá trị $j(E)$.
* Full script:
```py
E = EllipticCurve(GF(163), [145, 49])
print(E.j_invariant())
```
* **Flag: 127**
### Where's the Supersingular Curve
* 
* Script:
```py
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
from gmpy2 import *
from sage.all import *
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]
curves = []
for A in A_coefficients:
E = EllipticCurve(F, [0, A, 0, 1, 0])
curves.append(E)
if E.cardinality() == p + 1:
print(A)
```
* Hoặc 1 cách làm khác được tham khảo ở [đây](https://doc.sagemath.org/html/en/reference/arithmetic_curves/sage/schemes/elliptic_curves/ell_finite_field.html#sage.schemes.elliptic_curves.ell_finite_field.EllipticCurve_finite_field.is_supersingular)
```py
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(GF(2**127-1), [0, A, 0, 1, 0])
if E.is_supersingular():
print(A)
```
* **Flag:170141183460469230846243588177825628225**
### Image Point Arithmetic
* Áp dụng tính chất của phép đẳng cấu thôi: $𝜑(𝑃+𝑄)=𝜑(𝑃)+𝜑(𝑄)$
* 
```py
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
from gmpy2 import *
phi_P = (48622,27709)
phi_Q = (9460,13819)
p = 63079
x1,y1 = phi_P[0],phi_P[1]
x2,y2 = phi_Q[0],phi_Q[1]
m = ((y2-y1)*pow(x2-x1,-1,p))%p
x3 = (m**2 - x1 - x2)%p
print(x3)
```
* **Flag:37097**
### Montgomery Curves
* Tìm **Montgomery point** theo [doc này của sagemath](https://doc.sagemath.org/html/en/reference/arithmetic_curves/sage/schemes/elliptic_curves/ell_generic.html#sage.schemes.elliptic_curves.ell_generic.EllipticCurve_generic.montgomery_model)
* Script:
```py
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
from gmpy2 import *
from Crypto.PublicKey import ECC
p = 1912812599
a = 312589632
b = 654443578
E = EllipticCurve(GF(p), [a, b])
Ea = E.montgomery_model()
print(Ea)
```
* **Flag:723347356**
### DLOG on the Surface
* Ở đây có 1 khái niệm mới đó là [The Weil pairing](https://github.com/defeo/MathematicsOfIBC/blob/popayan-temp/poly.pdf). Mục 6 nhe :satisfied:
* 
* Nhưng [ở đây](https://www.sagemath.org/files/thesis/hansen-thesis-2009.pdf) thì nó lại không giống lắm :))
* 
* Nôm na thì **Weil pairing** $e_n(P,Q)$ là 1 phép ghép đôi 2 điểm $P,Q$ trong nhóm $E[n]$ thuộc cùng 1 đường cong Elliptic $E$.
* 1 số tính chất quan trọng của **Weil pairing**:
* **Song tuyến tính**: $e_n(aP,bQ)$ = $e_n(P,Q)^{ab}$
* **Luân phiên**: **Weil pairing** thỏa mãn $𝑒_𝑛(𝑃,𝑃)=1$ cho mọi $𝑃∈𝐸[𝑛]$.
* **Không suy biến**: Nếu $𝑒_𝑛(𝑃,𝑄)=1$ cho mọi $Q∈E[n]$, thì $P=(0:1:0)$.
* Script:
```py
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
from gmpy2 import *
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
iv = bytes.fromhex('6f5a901b9dc00aded4add3791812883b')
ct = bytes.fromhex('56ecb68a90cad9787a24a4511720d40d625901577f6d0f1eef9fc34cf042709110cdc061fff91e934877674a30ed911283b83927dbcc270ae358d6b1fe2d5bed18ce1b02d8805de55e5b36deb0d28883')
def decrypt_flag(a, b, c, d,iv,ct):
data_abcd = str(a) + str(b) + str(c) + str(d)
key = SHA256.new(data=data_abcd.encode()).digest()[:128]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ct)
return flag
from sage.all import *
p = 2**127 - 1
F.<i> = GF(p^2, modulus=[1,0,1])
E = EllipticCurve(F, [1,0])
P, Q = E.gens()
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))
n = p + 1
assert n == P.order() == Q.order()
e = P.weil_pairing(Q, n)
a = R.weil_pairing(Q, n).log(e) % n
b = -R.weil_pairing(P, n).log(e) % n
c = S.weil_pairing(Q, n).log(e) % n
d = -S.weil_pairing(P, n).log(e) % n
flag = decrypt_flag(a,b,c,d,iv,ct)
print(flag)
```
* Giải thích :
* Giá trị $e$ chính là $e_n(P,Q)$, là cơ sở gốc để tính toán logarithm rời rạc.
* Với giá trị $a$ tính như kia thì mình giải thích như sau:
* $R$.**wei_pairing**$(Q, n)$ = $e_n(R,Q)$
= $e_n(aP + bQ,Q)$
= $e_n(aP,Q)$ * $e_n(bQ,Q)$
= $e_n(P,Q)^a$ * $e_n(Q,Q)^b$
= $e_n(P,Q)^a$ * $1$ # do tính luân phiên.
= $e^a$
* Vậy tính $a$ thì thông qua phương thức **log(e)** thôi.
* Với giá trị $b$:
* $R$.**wei_pairing**$(P, n)$ = $e_n(R,P)$
= $e_n(aP + bQ,P)$
= $e_n(aP,P)$ * $e_n(bQ,P)$
= $e_n(P,Q)^a$ * $e_n(Q,P)^b$
= $1$ * $(e_n(P,Q)^{-b})$ # do tính luân phiên.
= $e^{-b}$
* Các giá trị $c,d$ còn lại cũng tính tương tự nhe.
* **Flag:Flag:crypto{now_try_writing_a_function_for_fast_torsion_basis_generation!}**
## Road to SIDH
### Two Isogenies
* 
* Script:
```py
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
from gmpy2 import *
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
p = 2**18 * 3**13 - 1
F.<i> = GF(p^2, modulus=[1,0,1])
E = EllipticCurve(F, [1,0])
K = E(i, 0)
phi = E.isogeny(K)
print(phi.codomain().j_invariant())
```
* **Flag:287496**
### Three Isogenies
* Dựa vào định lí **Vélu** ở trên thì ta có :
* Script:
```py
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
from gmpy2 import *
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
p = 2**18 * 3**13 - 1
F.<i> = GF(p^2, modulus=[1,0,1])
E = EllipticCurve(F, [1,0])
K = E(483728976, 174842350631)
K2 = 2 * K # Tính [2]K
# Bước 3: Tính toán các tham số t_Q, u_Q, w_Q cho từng điểm trong kernel
def compute_t_u_w(Q):
x_Q, y_Q = Q.xy() # Lấy tọa độ x, y của điểm Q
t_Q = 3 * x_Q^2 + E.a4() # t_Q = 3*x_Q^2 + A
u_Q = 2 * y_Q^2 # u_Q = 2*y_Q^2
w_Q = u_Q + t_Q * x_Q # w_Q = u_Q + t_Q*x_Q
return t_Q, u_Q, w_Q
# Tính các giá trị t_Q, u_Q, w_Q cho K và [2]K
t_K, u_K, w_K = compute_t_u_w(K)
t_K2, u_K2, w_K2 = compute_t_u_w(K2)
# Bước 4: Tính tổng t và w
t = t_K + t_K2 # Tổng t cho tất cả các điểm trong kernel (bỏ qua 0)
w = w_K + w_K2 # Tổng w cho tất cả các điểm trong kernel
# Bước 5: Tính hàm r(x)
def r(x):
return x + (t_K / (x - K[0])) + (u_K / (x - K[0])^2) + (t_K2 / (x - K2[0])) + (u_K2 / (x - K2[0])^2)
# Bước 6: Tính isogeny và đường cong đích E'
A_prime = E.a4() - 5 * t # A' = A - 5t
B_prime = E.a6() - 7 * w # B' = B - 7w
E_prime = EllipticCurve([A_prime, B_prime]) # Đường cong đích E'
# Bước 7: Tính j-invariant của E'
j_invariant = E_prime.j_invariant()
# Kết quả: j-invariant
print(j_invariant)
```
* Còn không thì code bài trên cũng không có gì thay đổi cả:
```py
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
from gmpy2 import *
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
p = 2**18 * 3**13 - 1
F.<i> = GF(p^2, modulus=[1,0,1])
E = EllipticCurve(F, [1,0])
K = E(483728976, 174842350631)
phi = E.isogeny(K)
print(phi.codomain().j_invariant())
```
* **Flag:96392670793**
### Composite Isogenies
* Script:
```py
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
from gmpy2 import *
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
p = 2**18 * 3**13 - 1
F.<i> = GF(p^2, modulus=[1,0,1])
E = EllipticCurve(F, [1,0])
K = E(357834818388*i+53943911829,46334220304*i+267017462655)
phi = E.isogeny(K,algorithm='factored')
print(phi.codomain().j_invariant())
```
* **Flag:249510360818*i + 292990704480**
### SIDH Key Exchange
* Đề bài đã cho chúng ta gợi ý về cách hoàn thiệu các hàm bị hidden rồi. Làm theo hướng dẫn thôi.
* Script:
```py
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
from gmpy2 import *
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
def decrypt_flag(shared_secret,iv,ct):
key = SHA256.new(data=str(shared_secret).encode()).digest()[:128]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ct)
return flag
ea, eb = 110, 67
p = 2**ea*3**eb - 1
F.<i> = GF(p**2, modulus=[1,0,1])
# Public curve
E0 = EllipticCurve(F, [1,0])
# Torsion points
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)
# Secret Keys
sA = 225902606209514408534212339057054
sB = 38410379124791756271891302485727
iv = bytes.fromhex('05a4cfbce59acb952128af83c9694390')
ct = bytes.fromhex('755b72b2e3bef2e7a4b2ce4a370f287ad04c1359bace25f3def8be23c0c49e89b4302408ad2dcb02d4875fe58c543d91')
KA = P2 + sA * Q2
KB = P3 + sB * Q3
phi_B = E0.isogeny(KB, algorithm='factored')
EA = phi_B.codomain()
phi_B_P2_value = phi_B(P2)
phi_B_Q2_value = phi_B(Q2)
K_SA = phi_B_P2_value + sA * phi_B_Q2_value
phi_A = E0.isogeny(KA, algorithm='factored')
EB = phi_A.codomain()
phi_A_P3_value = phi_A(P3)
phi_A_Q3_value = phi_A(Q3)
K_SB = phi_A_P3_value + sB * phi_A_Q3_value
phi_SA = EA.isogeny(K_SA,algorithm='factored')
phi_SB = EB.isogeny(K_SB,algorithm='factored')
assert phi_SA.codomain().j_invariant() == phi_SB.codomain().j_invariant()
flag = decrypt_flag(phi_SB.codomain().j_invariant(),iv,ct)
print(flag)
```
* **Flag:crypto{congratulations_you_are_an_isogenist!}**
### Breaking SIDH
* Sau 1 hồi đọc hết các **paper** người ta cho thì mình không hint được gì cả. :santa:
~~( Hoặc có thể do mình non )~~
* Sau 1 hồi vật vờ đi tìm thêm tài liệu thì mình có thấy được 1 [chall cũ](https://ctftime.org/writeup/36033) trên ctf time.
* Nó cũng tương tự gần hết đó. Và thêm quả đề bài gợi ý là **[Castryck-Decru-Attack](https://github.com/GiacomoPope/Castryck-Decru-SageMath/tree/main)** thì có vẻ nó legit :))
* Việc của mình là kết hợp 2 **link** trên để **recover secret key** của Alice và Bob thôi.
* Recover `Bob private key` dùng file **baby_SIDH.sage** nhe. Thêm các thông số của mình vào nữa.
* Script tìm Bob_key:
```py
from Crypto.Util.number import *
# from pwn import *
from tqdm import tqdm
from gmpy2 import *
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
# Local imports
import public_values_aux
from public_values_aux import *
# Load Sage files
load('castryck_decru_shortcut.sage')
# Base field
f, ea, eb = 45, 117, 73
p = f * 2**ea * 3**eb - 1
F.<i> = GF(p**2, modulus=[1,0,1])
i = F.gen()
# Parameter curve
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)
# Alice Public Key
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)
# Bob's Public Key
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)
public_values_aux.p = p
Fp2.<i> = GF(p^2, modulus=x^2+1)
R.<x> = PolynomialRing(Fp2)
a = ea
b = eb
check_torsion_points(E0, a, b, P2, Q2, P3, Q3)
E0.set_order((p+1)^2)
phi = EllipticCurveIsogeny(E0, x)
E1728 = phi.codomain()
for iota in E1728.automorphisms():
P = E1728.random_point()
if iota(iota(P)) == -P:
two_i = phi.post_compose(iota).post_compose(phi.dual())
print(two_i)
break
# ===================================
# ===== ATTACK ====================
# ===================================
def RunAttack(num_cores):
return CastryckDecruAttack(E0, P2, Q2, EB, phiB_P2, phiB_Q2, two_i, num_cores=num_cores)
if __name__ == '__main__' and '__file__' in globals():
if '--parallel' in sys.argv:
# Set number of cores for parallel computation
num_cores = os.cpu_count()
print(f"Performing the attack in parallel using {num_cores} cores")
else:
num_cores = 1
recovered_key = RunAttack(num_cores)
```
* 
* `Bob_key = 39990433064274301814750584859416466`
* Thực ra lúc đầu nếu gen **two_i** y như file **baby_SIDH.sage** thì lỗi tùm lum mà mình cũng không biết cách fix như nào ~~( chính xác là không biết vì sao không được)~~
* 
* Mình nghĩ là do đường cong của bài này khác, nên **two_i** khác nhau. Nhưng may mà [chall cũ trên CTF Time](https://ctftime.org/writeup/36033) có đưa ra cách tạo **two_i** phù hợp. Nên mình mút đoạn code đó là được code hoàn chỉnh tìm **private_key**.
* Đây nè :
* Việc còn lại thì đơn giản rồi .
* Script:
```py
from Crypto.Util.number import *
from gmpy2 import *
import math
from pwn import *
from tqdm import tqdm
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from hashlib import md5
import json
import time
from Crypto.Hash import SHA256
import os
import random
import os
import Crypto.Util.number as cun
# Base field
f, ea, eb = 45, 117, 73
p = f * 2**ea * 3**eb - 1
F.<i> = GF(p**2, modulus=[1,0,1])
i = F.gen()
# Parameter curve
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)
# Alice Public Key
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)
# Bob's Public Key
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 decrypt_flag(iv,ct,shared_secret):
key = SHA256.new(data=str(shared_secret).encode()).digest()[:128]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ct)
return flag
iv = bytes.fromhex('f45273daf12b8234bd41607d8b517913')
ct = bytes.fromhex('65917ae4d3de3ba753d50bab78992b2239cb189493807fcc3da8d058da1eda7d993c041d0ecb09089808d759a982f087')
sB = 39990433064274301814750584859416466
K = phiA_P3 + sB * phiA_Q3
E = EA.isogeny(K, algorithm="factored").codomain()
shared_secret = E.j_invariant()
flag = decrypt_flag(iv,ct,shared_secret)
print(flag)
```
* **Flag:crypto{welcome_to_the_future_of_isogenies}**
* Do mình lười ghép code nên chia thành 2 file. Các bạn thông cảm nhe.
* À còn 1 điều nữa là mình có thử recover lại cả **Alice_key** tương tự như trên nhưng không được. Mình cũng không biết tại sao nhưng lỡ ra flag rồi thì mình không tìm cách fix nữa. :vampire:
## Road to CSIDH
### Special Isogenies
* Bài này thì ta tìm điểm có $order = 5$ và tính đường cong $E'$ là kết quả của phép đẳng cấu $E$ với điểm vừa tìm được.
* Script:
```py
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
from gmpy2 import *
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
p = 419
F = GF(p)
E0 = EllipticCurve(F,[1,0])
P = None
for point in E0.points():
if point.order() == 5:
P = point
break
phi = E0.isogeny(P)
E_prime = phi.codomain()
Ea = E_prime.montgomery_model()
Ea
```
* **Flag:199**
### Prime Power Isogenies
* Nếu làm bằng **isogeny_ell_graph()**:
* Script:
```python
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
from gmpy2 import *
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
E0 = EllipticCurve(GF(419), [1,0])
print(E0)
# Xem xét đồ thị isogeny bậc 7
G7 = E0.isogeny_ell_graph(7, directed=False, label_by_j=True)
G7.plot()
```
* 
* Đếm tay thì được 27.
* Nếu muốn ra luôn kết quả thì:
```py
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
from gmpy2 import *
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
E = EllipticCurve(GF(419), [1, 0])
print(E.isogeny_ell_graph(7))
```
* **Note**:
* 1 cách làm khác là cứ đẳng cấu đường cong đó, tới khi nào về đường cong đó thì dừng:
```py
p = 419
Fp = GF(p)
E = EllipticCurve(Fp, (1, 0))
ctr = 0
j = E.j_invariant()
while E.j_invariant() != j or ctr == 0:
K = E.gen(0)
K *= (p+1)//7
phi = E.isogeny(K)
E = phi.codomain()
ctr += 1
print(ctr)
```
* **Flag:27**
### Secret Exponents
* Script:
```py
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
from gmpy2 import *
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
p = 419
F = GF(p)
# Định nghĩa đường cong Montgomery ban đầu
E0 = EllipticCurve(F,[1,0]) # y^2 = x^3 + x mod 419
print(E0)
for i in range(2):
P_order_3 = None
for point in E0.points():
if point.order() == 3:
P_order_3 = point
break
phi = E0.isogeny(P_order_3)
E0 = phi.codomain()
for i in range(3):
P_order_ = None
for point in E0.points():
if point.order() == 5:
P_order_5 = point
break
phi = E0.isogeny(P_order_5)
E0 = phi.codomain()
for i in range(4):
P_order_7 = None
for point in E0.points():
if point.order() == 7:
P_order_7 = point
break
phi = E0.isogeny(P_order_7)
E0 = phi.codomain()
Ea = E0.montgomery_model()
Ea
```
* **Flag:404**
### Twisted CSIDH Isogenies
* Cách làm đơn giản nhất đó là cứ đếm số lần để nó tiến được về đường cong cũ. Sau đó lùi 1 giá trị là tìm được đường cong cần tìm thôi.
```py
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
from gmpy2 import *
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
p = 419
Fp = GF(p)
E = EllipticCurve(Fp, (1, 0))
ctr = 0
j = E.j_invariant()
while E.j_invariant() != j or ctr == 0:
K = E.gen(0)
K *= (p+1)//3
phi = E.isogeny(K)
E = phi.codomain()
ctr += 1
for i in range(ctr-1):
K = E.gen(0)
K *= (p+1)//3
phi = E.isogeny(K)
E = phi.codomain()
Ea = E.montgomery_model()
Ea
```
* **Note**: Hoặc là dùng code lùi (vì nếu như có quá nhiều lần tiến thì code trên không tối ưu)
```py
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
from gmpy2 import *
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
p = 419
Fp = GF(p)
E = EllipticCurve(Fp, (1, 0))
E = E.quadratic_twist()
K = E.gen(0)
K *= (p+1)//3
phi = E.isogeny(K)
E = phi.codomain()
E = E.quadratic_twist()
print(E.montgomery_model().a2())
```
* **Flag:261**
### CSIDH Key Exchange
* Ờm ý tưởng bài này thì nó không có gì khó khăn cả. Nếu $e$ dương thì tiến $e$ lần ,$e$ âm thì lùi $e$ lần, $e = 0$ thì thôi. $e$ ở đây mình đại diện cho giá trị khóa $private$ của Alice,Bob.
* Script:
```py
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
from gmpy2 import *
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
def decrypt_flag(iv,ct,shared_secret):
key = SHA256.new(data=str(shared_secret).encode()).digest()[:128]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ct)
return flag
iv = bytes.fromhex("daf6cd181775664b099609789fb564c9")
ct = bytes.fromhex("3dd92e255c8e677f4a92226d09f56e2b2f567052ffd4f6f60200018454a83affc2e694c2bf2ad27da38f7f49b6e89928")
# CSIDH-512 prime
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)
E = EllipticCurve(F, [1, 0])
E0 = E
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]
assert len(ells) == len(a_priv) == len(b_priv)
def forward(l,e,E):
for _ in range(abs(e)):
K = E.gen(0)
K *= (p+1)//l
phi = E.isogeny(K)
E = phi.codomain()
return E
def backward(l, e, E):
E = E.quadratic_twist()
E = forward(l,e,E)
E = E.quadratic_twist()
return E
def gen(ells,key,E):
for i in tqdm(range(len(key))):
l = ells[i]
e = key[i]
if e>0:
E = forward(l,e,E)
elif e<0:
E = backward(l,e,E)
return E
E_A = gen(ells,a_priv,E)
E_B = gen(ells,b_priv,E)
share_secret_A = gen(ells,a_priv,E_B).montgomery_model().a2()
share_secret_B = gen(ells,b_priv,E_A).montgomery_model().a2()
# print(share_secret_A)
# print(share_secret_B)
assert share_secret_A == share_secret_B
flag = decrypt_flag(iv,ct,share_secret_A)
print(flag)
```
* **Flag:crypto{post_quantum_NIKE_isogenies_just_do_it}**
* **Note:**
* Chỉ cần thay đổi nhỏ ở hàm forward là rất nhanh. còn Script cũ là 2 tiếng.
```py
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
from gmpy2 import *
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
def decrypt_flag(iv,ct,shared_secret):
key = SHA256.new(data=str(shared_secret).encode()).digest()[:128]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ct)
return flag
iv = bytes.fromhex("daf6cd181775664b099609789fb564c9")
ct = bytes.fromhex("3dd92e255c8e677f4a92226d09f56e2b2f567052ffd4f6f60200018454a83affc2e694c2bf2ad27da38f7f49b6e89928")
# CSIDH-512 prime
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)
E = EllipticCurve(F, [1, 0])
E0 = E
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]
assert len(ells) == len(a_priv) == len(b_priv)
def forward(l,e,E):
for _ in range(abs(e)):
G = ((p + 1) // l) * E.random_point()
inf = E((0, 1, 0))
while G == inf:
G = ((p + 1) // l) * E.random_point()
E = isogeny_codomain_from_kernel(E, G)
return E
def backward(l, e, E):
E = E.quadratic_twist()
E = forward(l,e,E)
E = E.quadratic_twist()
return E
def gen(ells,key,E):
for i in tqdm(range(len(key))):
l = ells[i]
e = key[i]
if e>0:
E = forward(l,e,E)
elif e<0:
E = backward(l,e,E)
return E
E_A = gen(ells,a_priv,E)
E_B = gen(ells,b_priv,E)
share_secret_A = gen(ells,a_priv,E_B).montgomery_model().a2()
share_secret_B = gen(ells,b_priv,E_A).montgomery_model().a2()
# print(share_secret_A)
# print(share_secret_B)
assert share_secret_A == share_secret_B
flag = decrypt_flag(iv,ct,share_secret_A)
print(flag)
```
* Mất có vài giây:
* 
* Nguyên nhân: Vì dùng **isogeny_codomain_from_kernel(E, G)** thay cho
**phi = E.isogeny(K), E = phi.codomain()** sẽ nhanh hơn rất nhiều vì code cũ mình phải tính tất cả các **isogeny** : **phi = E.isogeny(K)**, sau đó mới tìm đường cong đích :
**E = phi.codomain()**, còn code mới thì chỉ cần tính từ **kernel** của điểm **G**.
## Isogeny Challenges
### What's My Kernel
* Bài này áp dụng 1 chút về phép biến đổi đồng cấu của đẳng cấu như sau:
* $𝜑(𝑃+n𝑄)=𝜑(𝑃)+n𝜑(𝑄)$
$<=>𝜑(R)=𝜑(𝑃)+n𝜑(𝑄)$
$<=>O=𝜑(𝑃)+n𝜑(𝑄)$ # điểm vô cực.
* Từ đó tìm $n$ bằng **discrete_log** thôi.
* Script:
```python
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
from gmpy2 import *
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
l_a, l_b = 2, 3
e_a = 216
e_b = 137
p = (l_a ^ e_a) * (l_b ^ e_b) - 1
F = GF(p ^ 2, name="i", modulus=[1, 0, 1])
E = EllipticCurve(F, [0, 1])
i, = F.gens()
E_A = EllipticCurve(F, [(7712764739056777529792987423646889337402217452473623818903331120045456102569165026218420598248767317603435401713968530490357307795*i+9758256230562931813080263636289065758287866439147365597646450723337045772222738857092908727407334585972591094553818411432094464777), (14111394476215446245563948462935499285975180615187777011147664203502283568940589822501200201326292294803458962166963919769448620180*i+13109242201116529741594122295056720779908966260700480865503735602954357430118695171517916549873840990587047235292662060447639572670)])
phi_a_P_b = E_A(23952894958295317549971106723685134737893696601669145219207726439639811367925016451999242069428068943047723238819908252774486766337*i + 4305462457135268462142264590143148158970142912257623729725051176173395849821915511030491264545144391647666649473524326829794956856, 22266818407313663485605006496877581796532115423284800341915760912566163458303144152456856269304745399393537962410019487747495397607*i + 4419726782686001239678340241398527123282988628405899347621803247232804830981975088769950625242092440018396292009058977329258215839)
phi_a_Q_b = E_A(831800239128719623934089118985220873854807542447712150093021613769936785750351133960474011564870745205073463311921316788621778431*i + 15402744117044645512001884312795650889329806711970659247428390301404175742876408129656571894858120059888562036870272272006051303602, 15910085843685894625838711841842809245031051484845379580040299498782585224630037907430690257895403864870016080008595192352518845469*i + 11737105265834767072297460524082128066585409511311853470189225057161817943162394756398035248684338249353988301973489992957376234646)
n = discrete_log(-phi_a_P_b,phi_a_Q_b,operation='+',ord=2**216)
flag = b'crypto{'+ long_to_bytes(n)+ b'}'
print(flag)
```
* Giá trị `ord` ở đây được hàm trong sagemath định nghĩa là `order()`
* **Flag:crypto{whoops_this_was_just_a_dlog}**
### André Encoding
* Ý tưởng bài này thì mình dùng cái này từ [cái này](https://github.com/defeo/MathematicsOfIBC/blob/popayan-temp/poly.pdf)
* Với **degree** $d$ = ${2^{64}*b}$. Còn lại các giá trị khác mình biết òi.
* Từ đó tìm từng kí tự của $flag$, chính là tìm từng giá trị $b.$
* Script:
```py
from Crypto.Util.number import *
# from pwn import *
from tqdm import tqdm
from gmpy2 import *
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from output import *
import string
import json
lcm = 8337245403447921335829504375888192675135162254454825924977726845769444687965016467695833282339504042669808000
# Andre's encryption curve
p = 37 * 2**64 * lcm - 1
F.<i> = GF((p, 2), modulus=[1,0,1])
E = EllipticCurve(F, [0,1])
E.set_order((p+1)**2)
# Generator data
P = E(2754452008418475544762931777380298061286322242088097042789979017337032668335152047250270118628626846112409632316814344852346179989*i + 300888031019145372993855450123312195268855753102882163072967372426589237335996165853668912727448513477444811191182550244111536735, 4048396253042221946332182039831591283289177370092736377609511682595711744157657185583897171948127827836521892887941707373829426385*i + 5574313210012278375687658199880462698154719575075630281638825753946911987283962578905520742770486366773314976292767579688991668535, 1)
Q = E(1914292834750542008365772941838940247194316211832948370075234167086803005671626788818592170824160266813720050022811399854833864570*i + 675917976944321956275103708696442108160242821688340828072457829850507425923003867371226253254729899087222613984510532839645132037, 1353413969699500553835259943514301405386193613479830974260135363453012387178560466458631824224103775101292443946360403995987929735*i + 2642848780435012471695812611372313188888541702956899224702856112971832879700145426992696527731460150858414996112482220450878252755, 1)
def json_to_points(data):
p = 37 * 2**64 * lcm - 1
F.<i> = GF((p, 2), modulus=[1,0,1])
E = EllipticCurve(F, [0,1])
E.set_order((p+1)**2)
P_x2, P_x1 = data['P']['x']
P_y2, P_y1 = data['P']['y']
Q_x2, Q_x1 = data['Q']['x']
Q_y2, Q_y1 = data['Q']['y']
P_x = P_x1*i+P_x2
P_y = P_y1*i+P_y2
Q_x = Q_x1*i+Q_x2
Q_y = Q_y1*i+Q_y2
A = ((P_y**2 - Q_y**2) - (P_x**3 - Q_x**3)) / (P_x - Q_x)
B = P_y**2 - P_x**3 - A*P_x
E0 = EllipticCurve(F, [A,B])
phi_P = E0(P_x,P_y)
phi_Q = E0(Q_x,Q_y)
return phi_P,phi_Q
flag = ""
for i in tqdm(range(len(data))):
phi_P,phi_Q = json_to_points(data[i])
n = p + 1
e_PQ = P.weil_pairing(Q, n)
e_phi_PQ = phi_P.weil_pairing(phi_Q, n)
for b in range(256):
e_fake = e_PQ ** (2**64*b)
if e_fake == e_phi_PQ:
flag += chr(b)
print(flag)
```
* **Flag:crypto{weil_pairings_and_isogenies_are_best_friends}**
* Việc tìm lại **degree** $d$ có lẽ là dùng **discrete_log** hoặc phương thức **.log()** được. Nhưng brute từng kí tự trong khoảng $(0,256)$ thì cũng không phải không là 1 cách.
* Thực ra lúc đầu mình có hướng làm như `7Rocky`
* Ý tưởng là làm như tương tự bài `What's My Kernel` sau 1 chút biến đổi. Nhưng 1 hồi lâu mình không **discrete_log** được nên quit.
### Better than Linear
* Lúc đầu bài này mà tính **j-invariant** như những bài trước, tức là thêm **algorithm='factored'** để tính **phi = E.isogeny(K,algorithm='factored')** nhanh hơn, thì vẫn rất lâu.
* Dựa vào [resource](https://velusqrt.isogeny.org/velusqrt-20200616.pdf) họ cho kết hợp với [doc này của sagemath](https://doc.sagemath.org/html/en/reference/arithmetic_curves/sage/schemes/elliptic_curves/hom_velusqrt.html), thì mình tìm được algorithm mới.
* Script:
```py
from Crypto.Util.number import *
# from pwn import *
from tqdm import tqdm
from gmpy2 import *
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
p = 92935740571
F.<i> = GF(p^2, modulus=[1,0,1])
E = EllipticCurve(F, [1,0])
K = E(11428792286*i+6312697112,78608501229*i+30552079595)
phi = E.isogeny(K,algorithm="velusqrt")
print(phi.codomain().j_invariant())
```
* **Flag:48495725269*i + 91493879515**
* Hoặc thay đổi nhỏ :
```py
from sage.schemes.elliptic_curves.hom_velusqrt import EllipticCurveHom_velusqrt
p = 92935740571
F.<i> = GF(p^2, modulus=[1,0,1])
E = EllipticCurve(F, [1,0])
K = E(11428792286*i+6312697112,78608501229*i+30552079595)
phi = EllipticCurveHom_velusqrt(E, K)
print(phi.codomain().j_invariant())
```
### Abelian SIDH
* Bài này thì mình phân tích qua chút nhé.
* **Alice** tạo 1 **kernel** là $R_A = P_A + r_A*Q_A$, với $r_A = randint(0,2^{216})$; $P_A,Q_A$ là 2 điểm **torsion** trong $E$ có **order** là $2^{216}$. Dùng **kernel** $R_A$ tạo 1 **isogeny** $ϕ_A: E→E_A$.
* **Bob** tạo 1 **kernel** là $R_B = P_B + r_B*Q_B$, với $r_B = randint(0,3^{137})$; $P_B,Q_B$ là 2 điểm **torsion** trong $E$ có **order** là $3^{137}$. Dùng **kernel** $R_A$ tạo 1 **isogeny** $ϕ_B: E→E_B$.
* Bước đầu là thế, lúc này phát sinh thêm 1 khái niệm nữa là [Dual Isogeny](https://www.johannesloher.com/assets/files/the_dual_isogeny.pdf)
* Mình đọc [cái này](https://github.com/defeo/MathematicsOfIBC/blob/popayan-temp/poly.pdf) thì tìm thấy thứ cần tìm, nói chung là chỉ cần tập trung vào :
* 
* Bởi vì ngoài điểm $G$, mình biết thêm 2 điểm nữa là
$G_A = \hat{\phi}_A(ϕ_A(G))$ và $G_B = \hat{\phi}_B(ϕ_B(G))$
* **secret** hay là **key** cần tìm là $\hat{\phi}_A(ϕ_A(G_B)) == \hat{\phi}_B(ϕ_B(G_A))$
* Thì dựa vào lí thuyết ở ảnh trên kia, ta có $\hat{\phi}∘\phi = deg(\phi)$,
tức là $\hat{\phi}(ϕ(G))$ là 1 **isogeny**: $G→deg(ϕ)*G$
* Vậy $ss_A = \hat{\phi}_A(ϕ_A(G_B)) = deg_{E_A}*G_B$
và $ss_B = \hat{\phi}_B(ϕ_B(G_A)) = deg_{E_B}*G_A$
* Các thông số $G_A,G_B$ ta đã có hết rồi, và $deg_{E_A} = 2^{216}$, $deg_{E_B} = 3^{137}$
* Hướng đi thi có rồi, nhưng code đầu tiên của mình như sau:
```py
from Crypto.Util.number import *
from gmpy2 import *
import math
# from pwn import *
from tqdm import tqdm
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from hashlib import md5
import json
import time
from Crypto.Hash import SHA256
import os
def decrypt_flag(iv,ct,shared_secret):
key = SHA256.new(data=str(shared_secret).encode()).digest()[:128]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ct)
return flag
q = 66755491218549620204451278063200785887258235588279474221852899550437797658031
l_a = 2
l_b = 3
e_a = 216
e_b = 137
p = (l_a^e_a)*(l_b^e_b)*q - 1
F2.<i> = GF(p^2, name="i", modulus=x^2 + 1)
E = EllipticCurve(F2, [1, 0])
assert E.order() == ((l_a^e_a)*(l_b^e_b)*q)^2
G = E(284525705055227305209171433354262326583483353932890396374082376039620293167347284486476175866841636870352172611140798770638607860891148421274491414781769460579269366987499711492224975722383693724998945327430*i + 1505732117301446306244456647291108872440150309218670346804336845746049737306166624890419953190750991745319605357809802251161115415632644954176702934116791663302337496487008464465331505899884564177127436954255, 625472529935654036223921391438157288453365901129930947294363367235040059593079687415091508012127435124029308811603045594581554202553372496400288438224966890629676977438466598167329973052918856464699791832852*i + 47601474380995597168525750969588840445021207583064647146015202571081375996653285276671081590297360068195022075982179758981719629604575131347969613756306189238588058541679309930305808586991507704997154990697)
G_A = E(145915727530405194858501908067004149119271866229283785406975016416179519229602788568667141925183452266785838962540142812802147635625676101175514899849797493269264848223662441310624736419729402940497825120237*i + 1533748059308705144310714561393710915956614748853476862053333584077154898976924918286121829477204193114912648083440468146059927048252528425215385159537835867940099628635191907783117733548735865422276573695218, 656719674393860055266665093366417148918321963096698533123174717175987252626915060808605094735026806850329522327826652620966999851633490540865097265418253240684956616735962641073964036624910359405679313489708*i + 490302124124650386804784052586997518905538316252777543910951879620272030423624850466647845982720942016728314763501909461493913896702433702500754925468172028448946982120646755275577481920301078776794371168597)
G_B = E(1209705123825944797424706693204961126627572686151810742258347886081638625448638105497078403972632468257771560008199660366766403135521387848010440242607303076906252061506260708306731383701626933759996941173340*i + 537724590651311821177236261188649254487089251825308677486473659020113976583058198202321844403441053376201647207507235530947009033534278463164627138966921647250586671610313221081772734966962022394188211283003, 1367872476957834066472473151204630310870430022944990391495388571666029738678807875104101405110532815608844154365211129918575751133383943176057655115213401058573552182736144971039914106924532010795316022407484*i + 141463228846250275591417528244274312774237222581958487884803845362529881760909336379832032450680371520382692035731593791400586793166353461101345019528851538537956908603557945503241721149516929742657035792134)
iv = bytes.fromhex("f81ce520adb3e49a834f711f8dbf5903")
ct = bytes.fromhex("2309ddcea639f3acf2503470ad44a33144afed4b8a76c06cca4eb0d01e2aa4a4bb76035f778b179421d59b5449786a994455b3a4638f4d58759be1a515dc950a")
ss_A = (l_a ** e_a) * G_B
ss_B = (l_b ** e_b) * G_A
assert ss_A == ss_B
flag = decrypt_flag(iv,ct,ss_A)
print(flag)
```
* Thì không ra flag, sau khi xem lại [Abelian_group](https://en.wikipedia.org/wiki/Abelian_group) và trong **Elliptic Curve** có tồn tại khái niệm là điểm đối xứng. Vậy thì có thể việc ánh xạ ngược lại sẽ không phải là
**isogeny**: $G→G$ mà còn có thể là $G→-G$ chăng :question:
:::spoiler
Có lẽ lí do là **isogeny** bảo toàn cấu trúc nhóm `Abel`, và do tính chất đối xứng của đường cong **elliptic**, cả hai điểm **G** và **−G** đều có vai trò tương đương trong nhóm `Abel` .
:::
* Script:
```python
from Crypto.Util.number import *
from gmpy2 import *
import math
# from pwn import *
from tqdm import tqdm
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from hashlib import md5
import json
import time
from Crypto.Hash import SHA256
import os
def decrypt_flag(iv,ct,shared_secret):
key = SHA256.new(data=str(shared_secret).encode()).digest()[:128]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ct)
return flag
q = 66755491218549620204451278063200785887258235588279474221852899550437797658031
l_a = 2
l_b = 3
e_a = 216
e_b = 137
p = (l_a^e_a)*(l_b^e_b)*q - 1
F2.<i> = GF(p^2, name="i", modulus=x^2 + 1)
E = EllipticCurve(F2, [1, 0])
assert E.order() == ((l_a^e_a)*(l_b^e_b)*q)^2
G = E(284525705055227305209171433354262326583483353932890396374082376039620293167347284486476175866841636870352172611140798770638607860891148421274491414781769460579269366987499711492224975722383693724998945327430*i + 1505732117301446306244456647291108872440150309218670346804336845746049737306166624890419953190750991745319605357809802251161115415632644954176702934116791663302337496487008464465331505899884564177127436954255, 625472529935654036223921391438157288453365901129930947294363367235040059593079687415091508012127435124029308811603045594581554202553372496400288438224966890629676977438466598167329973052918856464699791832852*i + 47601474380995597168525750969588840445021207583064647146015202571081375996653285276671081590297360068195022075982179758981719629604575131347969613756306189238588058541679309930305808586991507704997154990697)
G_A = E(145915727530405194858501908067004149119271866229283785406975016416179519229602788568667141925183452266785838962540142812802147635625676101175514899849797493269264848223662441310624736419729402940497825120237*i + 1533748059308705144310714561393710915956614748853476862053333584077154898976924918286121829477204193114912648083440468146059927048252528425215385159537835867940099628635191907783117733548735865422276573695218, 656719674393860055266665093366417148918321963096698533123174717175987252626915060808605094735026806850329522327826652620966999851633490540865097265418253240684956616735962641073964036624910359405679313489708*i + 490302124124650386804784052586997518905538316252777543910951879620272030423624850466647845982720942016728314763501909461493913896702433702500754925468172028448946982120646755275577481920301078776794371168597)
G_B = E(1209705123825944797424706693204961126627572686151810742258347886081638625448638105497078403972632468257771560008199660366766403135521387848010440242607303076906252061506260708306731383701626933759996941173340*i + 537724590651311821177236261188649254487089251825308677486473659020113976583058198202321844403441053376201647207507235530947009033534278463164627138966921647250586671610313221081772734966962022394188211283003, 1367872476957834066472473151204630310870430022944990391495388571666029738678807875104101405110532815608844154365211129918575751133383943176057655115213401058573552182736144971039914106924532010795316022407484*i + 141463228846250275591417528244274312774237222581958487884803845362529881760909336379832032450680371520382692035731593791400586793166353461101345019528851538537956908603557945503241721149516929742657035792134)
iv = bytes.fromhex("f81ce520adb3e49a834f711f8dbf5903")
ct = bytes.fromhex("2309ddcea639f3acf2503470ad44a33144afed4b8a76c06cca4eb0d01e2aa4a4bb76035f778b179421d59b5449786a994455b3a4638f4d58759be1a515dc950a")
for t_A in [-1,1]:
for t_B in [-1,1]:
ss_A = t_A*(l_a ** e_a) * G_B
ss_B = t_B*(l_b ** e_b) * G_A
try:
assert ss_A == ss_B
flag = decrypt_flag(iv,ct,ss_A)
if b'crypto' in flag:
print(flag)
except:
continue
```
* **Flag:crypto{wait_I_thought_this_was_the_post_quantum_section}**
### Dual Masters
* Ở đây đề bài có gợi ý về việc dùng **dual**.
* Mình có sử dụng và chỉnh sửa hàm `dual` của chall **Abelian SIDH** để tìm phép ánh xạ đối ngẫu , từ đó có $phi_A$, kết hợp bài đã cho $phi_B$ thì lại **discrete_log** như bài **What's My Kernel**.
* Script:
```py
from Crypto.Util.number import *
from gmpy2 import *
import math
from pwn import *
from tqdm import tqdm
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from hashlib import md5
import json
import time
from Crypto.Hash import SHA256
import os
import random
import os
import Crypto.Util.number as cun
# Define Curve params
l_a, l_b = 2, 3
e_a = 216
e_b = 137
p = (l_a ^ e_a) * (l_b ^ e_b) - 1
F = GF(p ^ 2, name="i", modulus=[1, 0, 1])
E = EllipticCurve(F, [0, 1])
i = F.gen()
assert E.order() == ((l_a**e_a) * (l_b**e_b)) ** 2
# Cofactors
c_a = l_b ^ e_b
c_b = l_b ^ e_b
P_a = E(20136586736114246501835971171967338480311516382940373533952481525296357878861783566151781007236212556832934545674854612011626195700*i + 17814453364935074861383131667083124325683937346696984368949852778058904726511787029450818202901070694186758274352723265991464877103 , 1271771361808985304712159481749593042413672298743174888306246138805367680531766658529560708954342114713164882433446311394561215114*i + 2458042406822607338623223129871544282558479021229618369701845857877994575575856044528094950443550864121494484286802649880921739708 , 1)
Q_a = E(21803015129321483945529412215838779132813252821045317544411028404348688068008744729098809691017674062502155948983091074705848044135*i + 13082212877505354759913698066147486474050693412889330975858763468321298287624363965619656101414455426060476491447329452631424163500 , 19506407896382533931237830326416853938397569146136935331864946437347935359679645132170606348699875016125904420682336351889485252410*i + 15043791945562477356073952628550508300788370803355011888730813281302739269433285656956641625470216196554392274696427278619285685068 , 1)
E_A = EllipticCurve(F, [(15647464439428927741867845580767694684222523016251895093602328385380654388145388778115672931157828708127948851349755210959710992823*i+18519701628642104957465933782270611113379500730906473687377196168245135786408360125497897711207297387671119962606217672095858390120), (7633645641925656224162547557120979142458288939027826632263622435013191750759424333538814072346087746161472785937079595640620414463*i+19378290131372561524504737884022331022393059506539098406878225963551347653933679233858710469551163367570754633517180433892819440342)])
phi_a_Q_b = E_A(15299431986544116565289603141128936730054296135592165196922848777121350286377485832136840240125657196209757793781083819580249068968*i + 17051219994281676546361123230640448840845340329176128231730176689245736814461968605143814113803812890865243421542880279156556244461 , 3998868285015588876268560462444888175225579707550791385515097131316476642530563104222732513021020953406505731356727753586817062110*i + 19576513237814293888726624230603574617889471255277258991796653332639293951210409486398735758705505503362959553658315915727351406457 , 1)
K = phi_a_Q_b
phi_hat = E_A.isogeny(K, algorithm="factored")
phi_hat = phi_hat.codomain().isomorphism_to(E) * phi_hat
phi_hat = phi_hat.dual()
phi_a_P_b = phi_hat(P_a)
for t_a in [-1,1]:
for t_b in [-1,1]:
n = discrete_log(t_a*phi_a_P_b,t_b*phi_a_Q_b,operation='+',ord=2**216)
flag = b'crypto{'+ long_to_bytes(n)+ b'}'
print(flag)
```
* **Flag:crypto{but_I_only_gave_one_point?!}**
### Meet me in the Claw
* Source:
```py
import os
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.Util.Padding import pad
FLAG = b"crypto{??????????????????????????}"
# Base field
ea = 35
eb = 29
p = 2**ea * 3**eb - 1
F.<i> = GF(p**2, modulus=[1,0,1])
# Public parameters
E0 = EllipticCurve(F, [1, 0])
P2 = E0(1956194174015565770794336*i + 1761758151759977040301838, 2069089015584979134622338*i + 203179590296749797202321)
Q2 = E0(2307879706216488835068177*i + 525239361975369850140518, 1834477572646982833868802*i + 733730165545948547648966)
P3 = E0(2162781291023757368295120*i + 1542032609308508307064948, 1130418491160933565948899*i + 904285233345649302734471)
Q3 = E0(365294178628988623980343*i + 1867216057142335172490873, 2141125983272329025279178*i + 1860108401614981479394873)
# Alice's public key
EAa = 2336060373130772918448023*i+63223462935813026254900
EAb = 202739861418983960259548*i+525917254309082638166498
EA = EllipticCurve(F, [EAa, EAb])
phiA_P3 = None # Missing!!
phiA_Q3 = None # Missing!!
# Bob's secret
sB = 495832856
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 = '9a030e6824e7ec5d66b3443920ea76cb'
ct = '7f11a2ca0359cc5f3a81d5039643b1208ac7eb17f8bd42600d1f67e474cd664dcb8624c94175e167acfe856f48be34bd'
```
* Bài này lúc đầu mình bế tắc khi không có 1 hướng gì khả thi, hoặc là dựa vào các bài trước :crying_cat_face:
* Lúc đầu mình có hướng là từ $E_0,E_A$, tức là từ **đường cong nguồn, đường cong đích** thì tìm lại phép isogeny giữa nó, hay đại loại là
tìm **K** từ `phi = E_0.isogeny(K, algorithm="factored")`. Kiểu kiểu vậy.
* Nhưng sau 1 hồi đọc các `doc,paper` mà **cryptohack** cho, kết hợp với cả tìm thêm bên **sagemath** thì mình không tìm được 1 code hay hàm build sẵn nào có thể thực hiện ý tưởng kia của mình. ~~Hoặc do mình gà~~:hand_with_index_and_middle_fingers_crossed:
* Ờ thì theo như kinh nghiệm chơi **cryptohack** của mình thì đôi lúc hint nằm ngay ở tên challenge.
* Mình thấy cái `Claw` gg dịch nó không ra nghĩa nên mình nghĩ đây là 1 tên cách attack. Tìm thử **claw attack in isogeny** thì mút được [github này](https://github.com/LearningToSQI/SQISign-SageMath/blob/main/mitm.py)
có vẻ legit.
* Nôm na là code này họ sẽ từ 2 đường cong $E_0,E_A$ trong đẳng cấu $2^k$,
(trong bài này là $2^{35}$), sử dụng thuật toán DFS để tính các **j_invariant_path** của cả 2 đường cong, sau đó đối chiếu với nhau , nếu 2 **j_invariant_path** mà khớp ( tạo ra 1 **path** để nối 2 đường cong $E_0,E_A$) thì lúc đó sẽ tìm được phép **isogeny** giữa 2 đường cong.
* Code này của họ còn khá tối ưu khi sử dụng [Man in the middle](https://vi.wikipedia.org/wiki/T%E1%BA%A5n_c%C3%B4ng_xen_gi%E1%BB%AFa), để làm giảm thiểu thời gian thực thi.
* Clone git về rồi chạy thôi, file **mitm.py** là file mình dùng để tìm phép **isogeny**, có rồi thì thêm các thông số của challenge cho để tính nốt **share_secret** là có :triangular_flag_on_post:
* Script:
```python
# Sage imports
# from sage.all import (
# floor,
# PolynomialRing,
# factor,
# EllipticCurveIsogeny,
# EllipticCurve,
# )
from sage.all import *
from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
def sqrt_Fp2(a):
"""
Efficiently computes the sqrt
of an element in Fp2 using that
we always have a prime p such that
p ≡ 3 mod 4.
"""
p = Fp2.characteristic()
i = Fp2.gens()[0] # i = √-1
a1 = a ** ((p - 3) // 4)
x0 = a1 * a
α = a1 * x0
if α == -1:
x = i * x0
else:
b = (1 + α) ** ((p - 1) // 2)
x = b * x0
return x
def quadratic_roots(b, c):
"""
Computes roots to the quadratic polynomial
f = x^2 + b * x + c
Using the quadratic formula
Just like in school!
"""
d2 = b**2 - 4 * c
d = sqrt_Fp2(d2)
return ((-b + d) * Fp2_inv_2, -(b + d) * Fp2_inv_2)
def generic_modular_polynomial_roots(j1):
"""
Compute the roots to the Modular polynomial
Φ2, setting x to be the input j-invariant.
When only one j-invariant is known, we
find up to three new j-invariant values.
This is fairly slow, but is only done
once per graph.
"""
R = PolynomialRing(j1.parent(), "y")
y = R.gens()[0]
Φ2 = (
j1**3
- j1**2 * y**2
+ 1488 * j1**2 * y
- 162000 * j1**2
+ 1488 * j1 * y**2
+ 40773375 * j1 * y
+ 8748000000 * j1
+ y**3
- 162000 * y**2
+ 8748000000 * y
- 157464000000000
)
return Φ2.roots(multiplicities=False)
def quadratic_modular_polynomial_roots(jc, jp):
"""
When we have the current node's value as
well as the parent node value then we can
find the remaining roots by solving a
quadratic polynomial following
https://ia.cr/2021/1488
"""
jc_sqr = jc**2
α = -jc_sqr + 1488 * jc + jp - 162000
β = (
jp**2
- jc_sqr * jp
+ 1488 * (jc_sqr + jc * jp)
+ 40773375 * jc
- 162000 * jp
+ 8748000000
)
# Find roots to x^2 + αx + β
return quadratic_roots(α, β)
def generate_kernels_prime_power(E, l, e):
"""
Compute a list of points of order
exactly l**e which should generate
all isogenies of degree l**e
"""
D = l**e
# P, Q = torsion_basis(E, D)
P, Q = E.torsion_basis(l**e)
# Send points of the form
# [x]P + Q
K = Q
yield K
for _ in range(D - 1):
K += P
K._order = ZZ(D)
yield K
# Send points of the form
# P + [lx]Q
K = P
yield K
lQ = l * Q
for _ in range(D // l - 1):
K += lQ
K._order = ZZ(D)
yield K
def generate_kernels_division_polynomial(E, l):
"""
Generate all kernels which generate cyclic isogenies
of degree l from the curve E.
Kernel generators are found by computing the roots
of the l-th division polynomial and lifting these values
to points on the elliptic curve.
"""
f = E.division_polynomial(l)
xs = [x for x, _ in f.roots()]
for x in xs:
K = E.lift_x(x)
K._order = ZZ(l)
yield K
def kernel_from_isogeny_prime_power(ϕ):
"""
Given a prime-power degree isogeny ϕ
computes a generator of its kernel
"""
E = ϕ.domain()
D = ϕ.degree()
# Deal with isomorphisms
if D == 1:
return E(0)
# Generate a torsion basis of E[D]
# P, Q = torsion_basis(E, D)
P, Q = E.torsion_basis(D)
# Compute the image of P,Q
imP, imQ = ϕ(P), ϕ(Q)
# Ensure we can use Q as a base
# for the discrete log
# TODO:
# Here we assume D is a prime power,
# this could fail for the general case
if not has_order_D(imQ, D):
P, Q = Q, P
imP, imQ = imQ, imP
# Solve the discrete log such that
# imP = -[x]imQ. `DLP` uses Weil
# pairing to shift the dlog to Fp4.
x = DLP(-imP, imQ, D)
return P + x * Q
def find_j_invs(j1, l, j_prev=None):
"""
Compute the j-invariants of the elliptic
curves 2-isogenous to the elliptic curve
with j(E) = j1
The optional param j_prev is used to
pass through the parent node in the
graph.
This is important to stop backtracking,
but we can also use it to reduce the degree
of the modular polynomial to make root
derivation more efficient.
"""
# TODO: only l=2 supported
if l != 2:
raise ValueError("Currently, `find_j_invs` is only implemented for l=2")
if j_prev:
roots = quadratic_modular_polynomial_roots(j1, j_prev)
else:
roots = generic_modular_polynomial_roots(j1)
# Dont include the the previous node to avoid backtracking
return [j for j in roots if j != j_prev]
def j_invariant_isogeny_graph(j1, l, e, middle_j_vals=None):
"""
A depth-first search of the isogeny graph.
For G1 where we compute the whole graph, dfs or bfs is
the same. But when we are looking for a collision in
the leaves, we can supply the end values from G1 as
middle_j_vals, and stop as soon as we find a collision.
This means for a isogeny of degree 2^k, the best case for
G2 would be computing only (k/2) nodes rather than the whole
graph!
Actual graph is a list of dictionaries, with levels as elements
of the list and nodes in the dictionary with node : parent_node
as data pairs.
"""
isogeny_graph = [{} for _ in range(e + 1)]
# Set the root of the graph
isogeny_graph[0][j1] = None
# Set stack for DFS
stack = [(j1, 0)]
while stack:
# Get a new element from the stack
node, level = stack.pop()
# Parent of node (for backtracking)
node_parent = isogeny_graph[level][node]
# Where we will store the next nodes
child_level = level + 1
# Set a bool to see if we should check the middle
check_middle = child_level == e and middle_j_vals is not None
# Compute all child nodes, except the node which
# goes back down the tree
node_children = find_j_invs(node, l, j_prev=node_parent)
# Compute a dictionary of child : parent nodes for this
# level in the tree.
for child in node_children:
# Add children node to graph
isogeny_graph[child_level][child] = node
# Return early when DFS finds the middle j_invariant
if check_middle and child in middle_j_vals:
return isogeny_graph, child
# New nodes to search through
if child_level != e:
stack.append((child, child_level))
return isogeny_graph, None
def j_invariant_path(isogeny_graph, j1, j2, e, reversed_path=False):
"""
Compute a path through a graph with root j1 and
last child j2. This is efficient because of our
data structure for the graph (simply e look ups
in a dictionary).
"""
# Make sure the end node is where we expect
assert j1 in isogeny_graph[0]
assert j2 in isogeny_graph[e]
j_path = [j2]
j = j2
for k in reversed(range(1, e + 1)):
j = isogeny_graph[k][j]
j_path.append(j)
if not reversed_path:
j_path.reverse()
return j_path
def isogeny_from_j_invariant_path(E1, j_invariant_path, l):
"""
Given a starting curve E1 and a path of j-invariants
of elliptic curves l-isogenous to its neighbour, compute
an isogeny ϕ with domain E1 and codomain En with
j(En) equal to the last element of the path
"""
# Check we're starting correctly
assert E1.j_invariant() == j_invariant_path[0]
# We will compute isogenies linking
# Ei, Ej step by step
ϕ_factors = []
Ei = E1
for j_step in j_invariant_path[1:]:
# Compute the isogeny between nodes
ϕij = brute_force_isogeny_jinv(Ei, j_step, l, 1)
# Store the factor
ϕ_factors.append(ϕij)
# Update the curve Ei
Ei = ϕij.codomain()
# Composite isogeny from factors
ϕ = EllipticCurveHom_composite.from_factors(ϕ_factors)
return ϕ
# ======================================== #
# Brute force ell isogenies between nodes #
# ======================================== #
def brute_force_isogeny_jinv(E1, j2, l, e):
"""
Finds an isogeny of degree l^e, between
two curves E1, and an unknown curve
with j-invariant j2
TODO: write this to be combined with
`BruteForceSearch` so we don't have so
much code duplication?
"""
# Compute the j-invariants of the end
# points
jE1 = E1.j_invariant()
# Degree of isogeny we search for
D = l**e
# Handle case when the curves are
# isomorphic
if D == 1:
if jE1 == j2:
F = E1.base()
E2 = EllipticCurve(F, j=j2)
return E1.isomorphism_to(E2)
else:
raise ValueError(
f"A degree 1 isogeny cannot be found, as the curves are not isomorphic"
)
# Enumerate through kernel generators
if e == 1:
kernels = generate_kernels_division_polynomial(E1, l)
else:
kernels = generate_kernels_prime_power(E1, l, e)
for K in kernels:
ϕ = EllipticCurveIsogeny(E1, K, degree=D, check=False)
Eϕ = ϕ.codomain()
jEϕ = Eϕ.j_invariant()
if jEϕ == j2:
return ϕ
raise ValueError(
f"No degree {D} isogeny found linking the curves E1 and curve with invariant j2"
)
def brute_force_isogeny(E1, E2, l, e):
"""
Finds an isogeny of degree l^e, between
two curves E1, and E2
TODO:
Currently only implemented for prime
power degrees
"""
# Degree of isogeny we search for
D = l**e
# Handle case when the curves are
# isomorphic
if D == 1:
if E1.is_isomorphic(E2):
return E1.isomorphism_to(E2), E1(0)
else:
raise ValueError(
f"A degree 1 isogeny cannot be found, as the curves are not isomorphic"
)
# Enumerate through kernel generators
if e == 1:
kernels = generate_kernels_division_polynomial(E1, l)
else:
kernels = generate_kernels_prime_power(E1, l, e)
for K in kernels:
ϕ = EllipticCurveIsogeny(E1, K, degree=D, check=False)
Eϕ = ϕ.codomain()
if Eϕ.is_isomorphic(E2):
iso = Eϕ.isomorphism_to(E2)
ϕ = iso * ϕ
return ϕ, K
raise ValueError(
f"[-] BruteForceSearch failed. No degree {D} isogeny found linking the curves E1 and E2"
)
# ============================================ #
# Claw-finding attack to recover mitm isogeny #
# ============================================ #
def claw_finding_attack(E1, E2, l, e):
"""
Finds a meet in the middle isogeny of
degree D, between two curves E1, E2
by searching along two halves of a
graph of j invariants
"""
# We'll search sqrt(l**e) from E1
# and E2 and find a curve in the
# middle.
# Let e2 >= e1, as dfs approach means
# we'll probably not compute all of
# the second graph.
e1 = floor(e / 2)
e2 = e - e1
# Coerce the elements from Fp4 to Fp2
# as Ei are supersingular, this is always
# possible.
j1 = Fp2(E1.j_invariant())
j2 = Fp2(E2.j_invariant())
# Compute the isogeny graph with root j1
isogeny_graph_e1, _ = j_invariant_isogeny_graph(j1, l, e1)
# The top level of the graph are the middle
# j-invariants we want to find a collision with
e1_middle_vals = set(isogeny_graph_e1[e1].keys())
# Compute the isogeny graph with root j1
# `j_invariant_isogeny_graph` will terminate as soon as
# it finds a j invariant with j_middle in e1_middle_vals
isogeny_graph_e2, j_middle = j_invariant_isogeny_graph(
j2, l, e2, middle_j_vals=e1_middle_vals
)
# If we didn't find a value in the middle, then there's
# no isogeny, or we have a bug!
if not j_middle:
raise ValueError(f"No isogeny of degree {factor(l**e)} linking E1 and E2.")
# Given the middle j-inv, compute paths from Ei → Middle
j1_path = j_invariant_path(isogeny_graph_e1, j1, j_middle, e1)
j2_path = j_invariant_path(isogeny_graph_e2, j2, j_middle, e2, reversed_path=True)
# Make sure both paths end in the middle
assert j1_path[-1] == j2_path[0]
# Construct a path from j(E1) to j(E2)
j_path = j1_path + j2_path[1:]
# Compute the isogeny from the j-inv path
ϕ = isogeny_from_j_invariant_path(E1, j_path, l)
# Fix the end of the isogeny with an isomorphism
E2ϕ = ϕ.codomain()
iso = E2ϕ.isomorphism_to(E2)
return iso * ϕ
def meet_in_the_middle_with_kernel(E1, E2, l, e):
"""
Wrapper for the Claw finding algorithm.
Additionally computes the kernel of the
recovered isogeny, which is needed in
SQISign for other computations.
Edge cases:
When e = 0 the curves are isomorphic,
so just compute the isomorphism and exit.
When e = 1, we can't do a mitm, so just
brute force all l-isogenies from one end.
"""
# Deal with isomorphisms
if e == 0:
ϕ = E1.isomorphism_to(E2)
return ϕ, E1(0)
# Mitm doesn't work if there's no middle to meet in
if e == 1:
ϕ, K = brute_force_isogeny(E1, E2, l, e)
return ϕ, K
ϕ = claw_finding_attack(E1, E2, l, e)
if ϕ == None:
raise ValueError(
f"[-] ClawFindingAttack failed. No isogeny of degree {factor(l**e)} linking E1 and E2."
)
K = kernel_from_isogeny_prime_power(ϕ)
return ϕ, K
import os
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.Util.Padding import pad
iv = bytes.fromhex('9a030e6824e7ec5d66b3443920ea76cb')
ct = bytes.fromhex('7f11a2ca0359cc5f3a81d5039643b1208ac7eb17f8bd42600d1f67e474cd664dcb8624c94175e167acfe856f48be34bd')
def decrypt_flag(iv,ct,shared_secret):
key = SHA256.new(data=str(shared_secret).encode()).digest()[:128]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ct)
return flag
ea = 35
eb = 29
p = 2**ea * 3**eb - 1
Fp2 = GF(p**2, modulus=[1,0,1], name = 'i')
Fp2_inv_2 = Fp2(1) / 2
(i,) = Fp2.gens()
E0 = EllipticCurve(Fp2, [1, 0])
P2 = E0(1956194174015565770794336*i + 1761758151759977040301838, 2069089015584979134622338*i + 203179590296749797202321)
Q2 = E0(2307879706216488835068177*i + 525239361975369850140518, 1834477572646982833868802*i + 733730165545948547648966)
P3 = E0(2162781291023757368295120*i + 1542032609308508307064948, 1130418491160933565948899*i + 904285233345649302734471)
Q3 = E0(365294178628988623980343*i + 1867216057142335172490873, 2141125983272329025279178*i + 1860108401614981479394873)
EAa = 2336060373130772918448023*i+63223462935813026254900
EAb = 202739861418983960259548*i+525917254309082638166498
EA = EllipticCurve(Fp2, [EAa, EAb])
sB = 495832856
phi = claw_finding_attack(E0, EA, 2, ea)
print(phi)
print(E0)
print(EA)
phiA_P3 = phi(P3)
phiA_Q3 = phi(Q3)
K = phiA_P3 + sB * phiA_Q3
E = EA.isogeny(K, algorithm="factored").codomain()
shared_secret = E.j_invariant()
flag = decrypt_flag(iv,ct,shared_secret)
print(flag)
```
* **Flag:crypto{clawing_our_way_to_victory}**
* Mình sẽ không nói là mình mất cả nửa ngày để run code này lấy flag chỉ vì hàm `decrypt_flag` của mình vẫn để là ~~`flag = cipher.encrypt(ct)`~~. :baby_chick:
### A True Genus
* Đọc qua source code của bài , thì **key** đem đi mã hóa **AES** cho **flag** chuyển sang bin, sau đó check nếu:
* bit = 1 : trả về 3 giá trị $E_A = [a]*E_0,E_B = [b]*E_0,E_{AB} = [a]*[b]*E_0$
* bit = 0 : trả về 3 giá trị $E_A = [a]*E_0,E_B = [b]*E_0,E_C = [c]*E_0$
với các giá trị $[a],[b],[c]$ là private .
* Thoạt đầu thì đọc source code xong thấy việc phần biệt 2 đường cong $[a]*[b]*E_0$ và $[c]*E_0$ rất khó, khi những gì đề bài cho rất mờ nhạt, với hàm **action()** thì random tùm lum, hàm **backdoor()** thì không biết giá trị **secret_marks**.
* Cũng giống như bài **Meet me in the Claw**, có lẽ hint nằm ngay ở tiêu đề thử thách. Nên sau khi tìm kiếm vài thứ đại loại liên quan tới từ **Genus** thì mình kiếm được [cái này](https://eprint.iacr.org/2020/151.pdf) .
* Chính xác thứ chúng ta cần đọc bắt đầu từ mục **Definition 4 (DDH-CGA)**
* 
* Ở đây người ta hướng dẫn mình cần tìm 1 phép $χ$ sao cho $χ(E_0,E_A) = χ(E_B,E_{AB})$ hoặc $χ(E_0,E_B) = χ(E_A,E_{AB})$, đồng nghĩa với việc không tồn tại 1 phép $χ$ nào để $χ(E_0,E_A) = χ(E_B,E_{C})$.
* Đến đây có thể tự code hay sao đó cũng được nhưng **paper** có đưa 1 [github](https://github.com/KULeuven-COSIC/group_action_DDH/blob/main/elliptic_DDH.m) viết bằng **Magma** cách triển khai hàm này nên mình mút luôn.
* 
* Script:
```py
from Crypto.Util.number import *
from gmpy2 import *
import math
# from pwn import *
from tqdm import tqdm
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from hashlib import md5
import json
import time
from Crypto.Hash import SHA256
import os
import random
import os
import Crypto.Util.number as cun
from hashlib import sha512
from sympy.ntheory.residue_ntheory import discrete_log
from output import data
def decrypt_flag(iv,ct,secret):
key = SHA256.new(int.to_bytes(int(secret), 8,'big')).digest()[:128]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ct)
return flag
def compute_supersingular_delta(E_0, E_test):
Fp.<x> = PolynomialRing(E_0.base_field())
a = E_0.a4()
r = (x^3 + a * x + E_0.a6()).roots()[0][0]
riso = (x^3 + E_test.a4() * x + E_test.a6()).roots()[0][0]
char = ((E_test.a4() + 3*riso^2)/(a + 3*r^2))^((p - 1) / 4)
return 1 if char == 1 else -1
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 = bytes.fromhex(data['iv'])
ct = bytes.fromhex(data['ct'])
challenge_data = data['challenge_data']
key = ""
for i in tqdm(range(len(challenge_data))):
EA = challenge_data[i]['EA']
a4_EA,a6_EA = EA['a4'][0],EA['a6'][0]
EA = EllipticCurve(Fp2, [a4_EA, a6_EA])
EB = challenge_data[i]['EB']
a4_EB,a6_EB = EB['a4'][0],EB['a6'][0]
EB = EllipticCurve(Fp2, [a4_EB, a6_EB])
EC = challenge_data[i]['EC']
a4_EC,a6_EC = EC['a4'][0],EC['a6'][0]
EC = EllipticCurve(Fp2, [a4_EC, a6_EC])
if compute_supersingular_delta(base,EA) == compute_supersingular_delta(EB,EC):
key += "1"
else:
key += "0"
secret = int(key[::-1],2)
flag = decrypt_flag(iv,ct,secret)
print(flag)
```
* **Flag:crypto{Gauss_knew_how_to_break_CSIDH???}**
:::info
* **Note** : Giải thích vì sao đoạn này là `secret = int(key[::-1],2)`, tức là phải đảo ngược **key**
* Lúc đầu mình cũng không phát hiện ra nhưng có lẽ do **for** đoạn này nó lmao:
* Ví dụ nhé : 
:::
Sign in with Wallet
Connect another wallet