Rating:
Normally, Alice should calculate $\phi_A(P_B)$and $\phi_A(Q_B)$, and send $(E_A,\phi_A(P_B),\phi_A(Q_B))$ to Bob.
But in this challenge, Alice sends more.
```python
Alice = (ϕ_A.codomain().a_invariants(), ϕ_A(P_B).xy(), ϕ_A(Q_B).xy(), ϕ_A(P_A).xy(), ϕ_A(Q_A).xy())
```
Alice : $(E_A,\phi_A(P_B),\phi_A(Q_B),\phi_A(P_A),\phi_A(Q_A))$
$E_A$ is obtained from Elliptic Curve $E$ and $S_A = P_A + k_A * Q_A$. It's important that $\phi_A$ has $S_A$ as kernel.
We can see that $\phi_A(P_A)+k_A*\phi_A(Q_A) == 0$ on $E_A$.
```python
A_P_A = E_A(ϕ_A(P_A).xy())
A_Q_A = E_A(ϕ_A(Q_A).xy())
A_P_A + k_A * A_Q_A
'''
(0 : 1 : 0)
'''
```
We can get $k_A$ if this DLP is solved, which is easy to do.
Since the order of $E_A$ is smooth, Pohlig-Hellman algorithm can solve it in a short time.
Let SageMath help us.
```python
import hashlib
from base64 import b64decode,b64encode
from Crypto.Cipher import AES
p = 2^216*3^137 - 1
F. = GF(p^2, modulus=x^2+1)
E = EllipticCurve(F, [0, 6, 0, 1, 0])
xQ20=0x000C7461738340EFCF09CE388F666EB38F7F3AFD42DC0B664D9F461F31AA2EDC6B4AB71BD42F4D7C058E13F64B237EF7DDD2ABC0DEB0C6C
xQ21=0x00025DE37157F50D75D320DD0682AB4A67E471586FBC2D31AA32E6957FA2B2614C4CD40A1E27283EAAF4272AE517847197432E2D61C85F5
yQ20=0x001D407B70B01E4AEE172EDF491F4EF32144F03F5E054CEF9FDE5A35EFA3642A11817905ED0D4F193F31124264924A5F64EFE14B6EC97E5
yQ21=0x000E7DEC8C32F50A4E735A839DCDB89FE0763A184C525F7B7D0EBC0E84E9D83E9AC53A572A25D19E1464B509D97272AE761657B4765B3D6
xP20=0x0003CCFC5E1F050030363E6920A0F7A4C6C71E63DE63A0E6475AF621995705F7C84500CB2BB61E950E19EAB8661D25C4A50ED279646CB48
xP21=0x001AD1C1CAE7840EDDA6D8A924520F60E573D3B9DFAC6D189941CB22326D284A8816CC4249410FE80D68047D823C97D705246F869E3EA50
yP20=0x001AB066B84949582E3F66688452B9255E72A017C45B148D719D9A63CDB7BE6F48C812E33B68161D5AB3A0A36906F04A6A6957E6F4FB2E0
yP21=0x000FD87F67EA576CE97FF65BF9F4F7688C4C752DCE9F8BD2B36AD66E04249AAF8337C01E6E4E1A844267BA1A1887B433729E1DD90C7DD2F
xQ30=0x0012E84D7652558E694BF84C1FBDAAF99B83B4266C32EC65B10457BCAF94C63EB063681E8B1E7398C0B241C19B9665FDB9E1406DA3D3846
xQ31=0x0000000
yQ30=0x0000000
yQ31=0x000EBAAA6C731271673BEECE467FD5ED9CC29AB564BDED7BDEAA86DD1E0FDDF399EDCC9B49C829EF53C7D7A35C3A0745D73C424FB4A5FD2
xP30=0x0008664865EA7D816F03B31E223C26D406A2C6CD0C3D667466056AAE85895EC37368BFC009DFAFCB3D97E639F65E9E45F46573B0637B7A9
xP31=0x0000000
yP30=0x0006AE515593E73976091978DFBD70BDA0DD6BCAEEBFDD4FB1E748DDD9ED3FDCF679726C67A3B2CC12B39805B32B612E058A4280764443B
yP31=0x0000000
Q_A = E(xQ20 + xQ21*i, yQ20 + yQ21*i)
P_A = E(xP20 + xP21*i, yP20 + yP21*i)
Q_B = E(xQ30 + xQ31*i, yQ30 + yQ31*i)
P_B = E(xP30 + xP31*i, yP30 + yP31*i)
# Computes an l^e-isogeny out of E from a set Ss of kernel generators
# as a composition of e l-isogenies
def computeIsogeny(E, Ss, l, e):
S_tmps = Ss
E_tmp = E
ϕ = None
for k in range(e):
R_tmps = S_tmps
for _ in range(e-k-1):
R_tmps = [ l*R_tmp for R_tmp in R_tmps ]
ϕ_k = E_tmp.isogeny(kernel=R_tmps)
S_tmps = [ ϕ_k(S_tmp) for S_tmp in S_tmps ]
E_tmp = ϕ_k.codomain()
if ϕ is None:
ϕ = ϕ_k
else:
ϕ = ϕ_k * ϕ
return ϕ
fAlice = ((0, 6, 0, 6001602663961206370988750155271268843249113105575064100544244329723627508642651491029799456469448718421085928092642609765039188242*i + 17122560027285283790825644308649714063340414789188915872095421354901510218060415163697310413170734130335144089439494750625538071980, 22241966002746626067354539975418232642475646213518284443509300453664841759671344583904727702765870170961054029730219838438930886730*i + 6295409890219768050656401214128285134680958664621604435525993857295024885942522198730338761351461854361939143813589229958450834937), (20693617845250531673791079572257479372406496374051176010221583150895284635664420984163027961195027146723306399733543575074371571546*i + 12579440504826227790399898461168329080116453795381885031938887599830693619864645875985379594607106805272063128287141040474324472579, 17003339040898697587060167865681315428279965204095022676751761236717662173320135824191474549296911745414760875386583097246892970743*i + 2450227209495560745928392442008559789430024267104386893781343959329588604681368476319376824183170770268590193199446339985032818433), (24196999226902675779045571226331502647086872832197399777068255320010293863359017283213324144431537822661506383681353187559191999771*i + 14031872773998733507298731440596005313939108957137912313429212267974724984039194243338858626174518892025349039167378718436374581722, 10067956801857468023514754660550671095579147019588599811273848235704360993890497575424172688000039308192770149207724142524545451074*i + 9704956586624341710808951764565861341114293792082683257320510639095567055930904001585984811139137392398321200917960531515122425604), (21482597851178884503353076937735588452957177768806776910812379517549572253101759233236102347370343956671258496673645283509995572850*i + 14096078902807078355928598956816130045619245790159384751176932745646753234211180941505758827833314091690388346935619473665442809259, 13679392986650554551011681934303695650088628896811869083453967966676089303335417699532232752393700725181942165609165070072195990421*i + 22303973329492411565669001646989446651767650420180177485066511378012378529261175557912535448570067170663048114739927772127080694786), (5031508630808576087782892353323275460174142373365249589846782383660521445945988018058115279743582819518492860550820586178080959929*i + 20361864043088022309832424954188288334129520236737890920001299362176525293198035690628699135584668073379687130832090636102750496003, 5326896702997677262072220524322872052674185107431056651996898750306495168544570294686542579294013185895403025686718275379409582021*i + 7018087072590614715963128743406699936749123349867893045580774389322712378049822434865393438816413618294542843639485193888664986503))
fBob = ((0, 6, 0, 2510377837984569005668272963938229152759212776314258952545654072169410901298850712372306096701112903052487282410712205434980682770*i + 1533616599018469519548641055342254252507904258735350043186382046019246639038089759129707675919612374167907298647004842048842483225, 13335813103700469160284801960413086144549776993448017319107340684719947118153850729369660724596130930055245047262733708054423015655*i + 17338799868192494405204548102094725343306200019012693785648257092061088427620739800739315465276207804594142456129224673452195357714), (2771195673566835722887342815479686444463738278075014443830431110033775598812266459191044593910730473384513927831673567602258951977*i + 14695642564069380381636057787623481658663045420929947439988595067986417545517691517441254145488869846179463754817003384192274626463, 18564301293503451778592169644157610474379393936432543000343986957900909392616771402521075243703340903344745798060095728893961976940*i + 19628333731314344646926186187873836263784148023213378217245128148326949516664862760385029489345376891188072162779569669305066964933), (22650214990480384681860370457554162699319780968761610136003430194938807060051700030135993836240770510069117319449743388225281444184*i + 3377155996988041268039072873935941531295378688722591082040326948052676519006168915555632884024981285908480033902758240587615693054, 17806681788782120983952163360625445316482360798557639190977860032884873427321883793075291472918577432082376117267831746467121303568*i + 21533180999838449404329422084189008931697041812999894837076670480949795196804840300494281304611360768987802541355649881398701758313))
(fE_A, fA_P_B, fA_Q_B, fA_P_A, fA_Q_A) = fAlice
fE_A = EllipticCurve(F, fE_A)
fA_P_A = fE_A(fA_P_A)
fA_Q_A = fE_A(fA_Q_A)
(fE_B, fB_P_A, fB_Q_A) = fBob
fE_B = EllipticCurve(F, fE_B)
fB_P_A = fE_B(fB_P_A)
fB_Q_A = fE_B(fB_Q_A)
# set a valve
fE_A.set_order((p+1)^2)
fk_A = discrete_log(fE_A(0) - fA_P_A,fA_Q_A,operation='+')
assert fA_Q_A * fk_A == fE_A(0) - fA_P_A
fB_S_A = fB_P_A + fk_A*fB_Q_A
jAlice = computeIsogeny(fE_B, [fB_S_A], 2, 216).codomain().j_invariant()
iv = b'XSglnu+2ZwFuHGE8ddIuJQ=='
ct = b'4VR9ty+lFW6oQoWTVHiDE7A9uKw0KbQzpnCWOGVQXGo='
sk = hashlib.sha256(str(jAlice).encode('ascii')).digest()[:16]
cipher = AES.new(sk, AES.MODE_CBC,iv = b64decode(iv))
flag = cipher.decrypt(b64decode(ct))
print(flag)
'''
b'union{al1c3_in_t0r51ongr0upl4nd}'
'''
```
