拖延症犯了，拖了好久
ECC
简介
$ECC（Elliptic\; Curve \;Cryptography）$是基于椭圆曲线离散对数问题
最常用的椭圆曲线方程是定义在p为素数的有限域Zp上的同余方程
$$ y^2=x^3 + ax + b\;(mod\;p) \\ 其中a,b \in Z_p,4a^3+27b^2\neq0 \;mod \;p $$
可以用$E_p(a,b)$表示，限定条件主要保证在实数域上曲线方程有三个不同的点
这个方程称为椭圆曲线的维尔斯特拉斯标准形式$（Weierstrass\; normal \;form）$
椭圆曲线加法的定义
- 取无穷远点$O$为单位元
- 任意$P,Q,R\in E\;$，且三点共线，则$P+Q+R=O$
- 若$P(x,y)\in E\;$,则$P$的逆元定义为$-P=(x,-y)\in E$
- 若$P,Q\in E\;且P_x\neq Q_x$，则$P+Q\;$表示：过$P,Q$做一条直线，交$E$于一点$R$。由于$P\neq Q$，所以$R$点唯一。因此$P+Q+R=O$，即$P+Q=-R$，含义为：$P+Q$是$P,Q$之间的连线与$E$交点关于$x$轴的对称点
加法的具体计算公式
$$ \lambda =\begin{cases} \frac{y_2-y_1}{x_2-x_1} mod\; p \qquad & P\neq Q \\ \frac{3x_1^2+a}{2y_1} mod \;p \qquad & P = Q \end{cases} $$
$$ \begin{aligned} &x_3=\lambda^2-x_1-x_2 (mod \;p)\\ &y_3=\lambda(x_1-x_3)-y_1 \end{aligned} $$
加密和解密
任取$g \in E_p(a,b)$，选择一个实数$x<p$，计算
$$y=xg$$
因此，公钥为$(g,p,y)$，私钥为$x$
加密过程:
对于明文$m$，随机选择正整数$k<p$，计算
$$ \begin{aligned} &c_1=kg\\ &c_2=m+ky \end{aligned} $$
密文为$(c_1,c_2)$
解密过程：
$$ m=c_2+(-xc_1) $$
验证：
$$ c2+(-xc1)=(m+ky)+(-xkg)=(m+kxg)+(+xkg)=m $$
DH密钥交换
$DH（Diffie-Hellman）$密钥交换算法的作用是使通信双方可以在不安全的通道中建立一个相同的密钥，用于加密通信
基本原理
通信双方约定一个素数$p$和一个$g$，$g$是$p$的一个原根
具体流程：
- 用户A选择一个随机数$a，1\leq a\leq q-2$，计算$S_A=g^a \;mod \;p$，并将$S_A$发送给用户B
- 用户B选择一个随机数$b，1\leq b\leq q-2$，计算$S_B=g^b \;mod \;p$，并将$S_B$发送给用户A
- 用户A收到收到$S_B$,计算$K_A=(S_B)^a\; mod \;p$
- 用户B收到收到$S_A$,计算$K_B=(S_A)^b\; mod \;p$
验证$K_A=S_B^a\; mod \; p=(g^b)^a\; mod \;p=(g^a)^b\; mod \; p=S_A^b\;mod \;p=K_B$
$DH$密钥交换算法无法验证对方身份，所以$DH$密钥交换算法不能抵御中间人攻击
ECDH
$ECC$加密算法和$DH$秘钥交换算法结合使用，用于密钥协商，这个密钥交换算法称为$ECDH$
双方会约定一条椭圆曲线$E_p(a,b)$和点$G$，$G\in E_p$
中国剩余定理
中国剩余定理（孙子定理，$Chinese\; Remainder \;Theorem$）是中国古代求解一次同余式组的方法。是数论中一个重要定理。
具体原理
设正整数$m_1,m_2,...,m_n$两两互素，则同余方程
$$ x \equiv a_1\; (mod\; m_1) \\ x \equiv a_2\; (mod\; m_2) \\ .\\ .\\ .\\ x \equiv a_n\; (mod\; m_n) $$
存在整数解，并且在模$M=m_1*m_2*...*m_n$下的解唯一，解为：
$$ x=a_1M_1M_1^{-1}+a_2M_2M_2^{-1}+...+a_nM_nM_n^{-1} \;(mod \; M) \\ 其中M_i=\frac{M}{m_i}，M_i^{-1}为M_i模m_i的逆元 $$
Invalid Curve Attack
我们可以看到椭圆曲线上的加法定义没有用到参数b，如果不检查点的合法性，运算就可能在另外一条曲线上（a相同，b不同)
若用户A为服务器，如果要获取服务器的选择的随机数a，可以采用$Invalid \;Curve\;Attack$方法
攻击思路
已知曲线$E_p(a,b)和曲线的阶q$
寻找不同的$b'$，使得$E_p(a,b')$的阶可以被一些小素数$p_i$整除
要求$p_1*p_2*...*p_n>q^2$
因此，曲线$E_p(a,b')$上存在点$G_i$的阶数为$p_i$
若服务器的随机数为$s$，那么我们可以得到$s*G_i$，计算$t，t<p$，使得$s*G_i=t*G_i$
即$s=t\; mod \; p_i$或者$-s=t\;mod\;p_i$，有双解，可以平方
$s^2=t^2\; mod\; p_i$
对于所有的$i=1,2,...,n$，获得$s^2=(t_i)^2\;mod\;p_i$，且$s^2<q^2$
再利用中国剩余定理CRT，计算出$s^2$，从而得到$s$
de1ctf2020 ECDH
提供了一个$task.py$脚本，实现了简易的$EDCH$的秘钥交换，要求获取服务器的$secert$
服务器允许交互91次，所以只能45组（$Exchange + Encrypt$）
所给的椭圆曲线如下
p = 0xdd7860f2c4afe6d96059766ddd2b52f7bb1ab0fce779a36f723d50339ab25bbd
a = 0x4cee8d95bb3f64db7d53b078ba3a904557425e2a6d91c5dfbf4c564a3f3619fa
b = 0x56cbc73d8d2ad00e22f12b930d1d685136357d692fa705dae25c66bee23157b8计算出$E_p(a,b)$的阶:
q=0xdd7860f2c4afe6d96059766ddd2b52f94b11044d70ebc8e8874e1952d141d4b3寻找$b'$
使用sagemath，来计算椭圆曲线的阶
p = 0xdd7860f2c4afe6d96059766ddd2b52f7bb1ab0fce779a36f723d50339ab25bbd
a = 0x4cee8d95bb3f64db7d53b078ba3a904557425e2a6d91c5dfbf4c564a3f3619fa
for b in range(1,120):
E=EllipticCurve(GF(p),[a,b])
print(b,E.order())由于sagemath中的facotr比较慢，可以添加到 https://www.alpertron.com.ar/ECM.HTM 里去分解，得到如下$b和p_i$（这里我就直接放上别人寻找的$b'$）
# b prime
[
(4, 2333),
(4, 5657),
(6, 499),
(7, 1103),
(9, 10903),
(11, 719),
(14, 853),
(14, 1567),
(19, 1373),
(20, 431),
(21, 661),
(23, 1291),
(26, 8191),
(28, 467),
(30, 6073),
(32, 2281),
(32, 9241),
(36, 487),
(37, 4513),
(42, 4621),
(44, 439),
(50, 14407),
(53, 929),
(55, 2729),
(62, 617),
(65, 25189),
(65, 26099),
(66, 881),
(66, 1009),
(73, 8117),
(86, 10301),
(91, 1693),
(96, 2069),
(98, 2357),
(99, 14741),
(100, 1663),
(102, 1447),
(106, 23929),
(107, 953),
(108, 16189),
(109, 1783),
(111, 13099),
(112, 5527),
(112, 2617),
(117, 8737),
]可以验证$p_1*p_2*…*p_n>q^2$
寻找阶为$p_i$的点
bb = [
(4, 2333), (4, 5657), (6, 499), (7, 1103), (9, 10903), (11, 719), (14, 853), (14, 1567), (19, 1373), (20, 431),(21, 661), (23, 1291), (26, 8191), (28, 467), (30, 6073), (32, 2281), (32, 9241), (36, 487), (37, 4513),(42, 4621), (44, 439), (50, 14407), (53, 929), (55, 2729), (62, 617), (65, 25189), (65, 26099), (66, 881),(66, 1009), (73, 8117), (86, 10301), (91, 1693), (96, 2069), (98, 2357), (99, 14741), (100, 1663), (102, 1447),(106, 23929), (107, 953), (108, 16189), (109, 1783), (111, 13099), (112, 5527), (112, 2617), (117, 8737)
]
Gs = []
for b, prime in bb:
E = EllipticCurve(GF(p), [a, b])
order = E.order()
P = E.random_point()
zero=P-P
while True:
G = P * (order // prime)
if G == zero:
P = E.random_point()
else:
break
print(G)
Gs.append((G[0], G[1]))
print(Gs)这里我们就得到了不同椭圆曲线上特定阶的点集$G_i$
秘钥交换
服务器用他的私钥$secret$算出共享密钥$s*G_i$，然后用这个共享秘钥加密数据，由于加密数据使用异或，且前256位为x，后256位为y。
所以我们可以使用512位全为1的明文，然后就可以通过密文推出共享秘钥$s*G_i$，由于这些$G_i$的阶很小，可以计算$t，t<p$，使得$s*G_i=t*G_i$，即$s^2=t^2\; mod \; p_i$
一共45组，会得到45组同余方程
计算secret
使用中国剩余定理（CRT）来解出同余方程的解$s^2$，最后开方得到$s$
exp.py
#!/usr/bin/python
# -*- coding: utf-8 -*-
# @Author: 丶墨宇棋
# @Contact: 1225097257@qq.com
# @Time: 2020/05/02
from pwn import *
from hashlib import sha256
from gmpy2 import invert, iroot
import string
from functools import reduce
context.log_level = 'debug'
s = remote('127.0.0.1', 8848)
q = 0xdd7860f2c4afe6d96059766ddd2b52f7bb1ab0fce779a36f723d50339ab25bbd
a = 0x4cee8d95bb3f64db7d53b078ba3a904557425e2a6d91c5dfbf4c564a3f3619fa
b = 0x56cbc73d8d2ad00e22f12b930d1d685136357d692fa705dae25c66bee23157b8
zero = (0, 0)
res = []
cipher = []
x = 0
y = 0
def add(p1, p2):
if p1 == zero:
return p2
if p2 == zero:
return p1
(p1x, p1y), (p2x, p2y) = p1, p2
if p1x == p2x and (p1y != p2y or p1y == 0):
return zero
if p1x == p2x:
tmp = (3 * p1x * p1x + a) * invert(2 * p1y, q) % q
else:
tmp = (p2y - p1y) * invert(p2x - p1x, q) % q
x = (tmp * tmp - p1x - p2x) % q
y = (tmp * (p1x - x) - p1y) % q
return (int(x), int(y))
def mul(n, p):
r = zero
tmp = p
while 0 < n:
if n & 1 == 1:
r = add(r, tmp)
n, tmp = n >> 1, add(tmp, tmp)
return r
def burte_sha(c, half):
stri = string.ascii_letters + string.digits
for i in stri:
for j in stri:
for z in stri:
for y in stri:
test = i + j + z + y + half
if sha256(test.encode()).hexdigest() == c:
print("sha256(" + test + ")==" + c)
return i + j + z + y
return False
def less1(s):
sh = s.recvuntil("XXXX:").decode()
pos1 = sh.find('+')
pos2 = sh.find(')')
pos3 = sh.find('\n')
half = sh[pos1 + 1:pos2]
c = sh[pos2 + 5:pos3]
res = burte_sha(c, half)
s.send(res)
def recvall(s):
s.recvline()
s.recvline()
q = s.recvline()[3:-1].decode()
a = s.recvline()[3:-1].decode()
b = s.recvline()[3:-1].decode()
P = s.recvline()[4:-2].decode().split(',')
Q = s.recvline()[4:-2].decode().split(',')
s.recvuntil("X:\n")
log.info('q:' + q)
log.info('a:' + a)
log.info('b:' + b)
log.info('P:(' + P[0] + ',' + P[1] + ')')
log.info('Q:(' + Q[0] + ',' + Q[1] + ')')
def Exgcd(r0, r1): # calc ax+by = gcd(a, b)
x0, y0 = 1, 0
x1, y1 = 0, 1
x, y = r0, r1
r = r0 % r1
q = r0 // r1
while r:
x, y = x0 - q * x1, y0 - q * y1
x0, y0 = x1, y1
x1, y1 = x, y
r0 = r1
r1 = r
r = r0 % r1
q = r0 // r1
return x
def CRT(mi, ai):
assert (isinstance(mi, list) and isinstance(ai, list))
M = reduce(lambda x, y: x * y, mi)
ai_ti_Mi = [a * (M // m) * invert(M // m, m) for (m, a) in zip(mi, ai)]
return reduce(lambda x, y: x + y, ai_ti_Mi) % M
def Exchange(s, msg):
s.sendline(str(msg[0]))
s.recvuntil("Y:\n")
s.sendline(str(msg[1]))
def Encrypt(s, msg):
s.recvuntil('message(hex):\n')
s.sendline(msg)
s.recvuntil('The result is:\n')
c = s.recvline().decode()
log.info('cipher:' + c)
cipher.append(c)
def Backdoor(s, m):
s.recvuntil("secret:\n")
s.sendline(m)
print(s.recvuntil("flag:\n"))
fg = s.recvline()
print(fg)
def deal_cipher(c, prime, GG):
bin_c = bin(int(c, 16))[2:]
bin_c = bin_c.rjust(512, '0')
assert len(bin_c) == 512
a = bin_c[:256]
b = bin_c[256:]
x = ''
y = ''
for i in a:
if i == '1':
x += '0'
else:
x += '1'
for i in b:
if i == '1':
y += '0'
else:
y += '1'
z = (int(x, 2), int(y, 2))
for i in range(prime):
S = mul(i, GG)
if S == z:
res.append(pow(i, 2, prime))
def chioce(s, c, msg):
s.recvuntil('choice:\n')
s.sendline(c)
eval(c)(s, msg)
def init_all():
Gs = [(52774744453568950865611407867917119171359684918671646722382499648762218034757, 15377825601731419254640229746912926783559096767382243161816075415636572160003), (96326121733313590050014060073073105518651977782581958811596553898426699138888, 27348742899809846016945820366686870801882887021045677737837514058531399423674), (94628316765602891122148862532769509981913743218525656044986318574020554616253, 25117407712775273669029355158414497599027552989312006186011138049917309486005), (21907417660626518953945378501165640656842450126114063952890357940292381235109, 73981949011674249978089354345070809134221381412587945041998907525878136544536), (29533143698732493850109472600143157431388908453658969362894588839397308513277, 24474271612812033255810181977991743017059819667982310946629346049193083352283), (87505008458559429049460006875325463672511109085669095013886591659698245652844, 56124281492104369502163328632167238691965935674240371560445189531847519192778), (68302841832832048103625595913159061259696800463639748922126392386785987271517, 71252705230962741988834581729292787183491434857950204313350214425168874942662), (28122881591072665533348439344425780744900704545529027048507508943958630881883, 9017539447258233755247585913118306425051873742299227748780474065585791158168), (72215521568280356681681303964685489811957583114685725736778200520554511157230, 49068750965385202667446501455658087538343523118885245732595148231849247599540), (24703914441351493520621648399954823665575807070430582175910843304330645280799, 57637902008168941622988292594161872792798055888949819197165504147699030264327), (55527517664704369813867540908013285051159548800438216485311183061671784301885, 99250078797003888531556349276955637619434370592741091037986392454527493179516), (30112918062171178243960648969541083574473333627693403563088250350731430513178, 27953274976149760245502353922802507458246469760128420508000652384906235238258), (96773525259873134289265155997215642817210958179976406217943459967974564758184, 50678543191833477412158840366867003337033972300267249014393496224534633675256), (82048129317434109251804287448660530951238819886905649829727103123348615854213, 81351101081758329449638873518082158301320293612619608024481811612794373961731), (49961733695176940335016109182872513138935725613758411931367570842081815688577, 42109473418248058040735958489397299404709032769907527680276061921201913191542), (36097793385843290867565125644857901083381109860764634484108324979433297438423, 27566975418520108310122266741411199065450405999854401570336736136093636185183), (88449670111597868783182433573136953541318632299867212407947642123014600953606, 86004943309292429309841324427003712777575628536300723544962810962827113208730), (72804325838415977760329881098886913830311714499128365561105403885171991647885, 15276778305934048296479946991182381223437439955604448135504979518831062900341), (25751361049245509758591661594220870906043840644960449154007707750703520380642, 17303025574220375868339457739856667013944654028710197470837511853899068954897), (49435571927929012400568957835100849447901102686406708571529543706688832947872, 90340809757983512919905454925813957633459877048479717480373535299814941970901), (87983405763902596450825683680939337152890843307305622306708498271657788039263, 58269001928495310723324109092704103481582942531190063286373459783535340339803), (79865464777127816077206388807053949487719615279400836828382861242269835546537, 78022515196568898370863070264739547187622905030217801045679177342327240303851), (8000471675511460387022515760507468873235705225976768004913335780959869483154, 25344501179212147310180933747525593956252691847634699720648489716372697383624), (55394777373718413150280325836559397981678134300653725768666478874664221248780, 69530493004753145779730365462495612165185907023827993062878406999406736364902), (63642284532096760114266411471835699856123369515193645068765739516044281119455, 28559966078614519237717434651239821367703416444530030571230581713812317715808), (55526865850411502606118972005563865737064782539819136342837482367285838033555, 62069758429524621875130321549996090710866518615999041639576610085740136297288), (53176267170596330589371374718695786713057687212694324993694725025509417217926, 22787451366100146325023081187922667713915548809905205473824003317124459676402), (24393623654856387989278120488560215511148576359495767940408633397014770633318, 83962583900532113564826029485363125215472660160514053665456813681810905853492), (24062889921380282311654577523260206864995467602759619736543612495429057452259, 94606817729184568292490583833374859051765884463002907617471932088925270370754), (41480991499962561855480236847799312133199139830758154071492344372925106642180, 83993792679998093633956191119249197999638738378888435268726625360236389572674), (33099042933814582850086461763917279433627036566735498321931725936383184955212, 78756135303559942636676252990382417510341273228022186096954707772399121048625), (99174914418076627154607675644701215042553179058805243730243160401039442110658, 32289135376353589405165992814612383356625066955055115050778625994667492827991), (29702846143480842637350163524424880856266066326808464533998349702990437838611, 82995842398606563657457209686103435660875700333643123815362364189376200523272), (61160197755172213845459808343478348633887524979802068297972810049216709959404, 82002997784566293029060409201655177112836602055348805737098123299834118028078), (15718922863999119952890141251820001968818657609502131139044053293552233046134, 2453441624758566580453788984696764623039565100973003950630372889684936394996), (96553635299396911730573277303961143613405257178895162871516293443831638587585, 94013204835204477279741083965415764389293553341861248353099155084240408860346), (24277736673125776996310144166105151238365456853387884082465743940822174647366, 46550671637322273170127346006505935783894248821226373852091016885269263009729), (44977136371912367230672262021807408925804791461257069426564371588271070405227, 36583300108534857510475725185953675202471275447108912711011546917898584387705), (43872799966483074542549165045328381456996839462806983673339896389849196035106, 2375502330749609876854814275110727325811419173700169636671657540326636017836), (68185588856194555268405910744480727379554069893841617443003542162253733144591, 69828986335758652492311608368453124958813434545539354146639278210635198185901), (28220674679662382683363467300486318731651626264559707828884703537093844171074, 35655051338262872700114741944499293735871563167421616535913704654132658387496), (45892145034352333044384831984316247614954385576664026886266278425490911796227, 88071519782363155047694398853343763838715255666567596626999874562346957646973), (27411624374916799710218430966742433934071674737837010362865031116732996875426, 89856396839344110380302094851617149648592128592557929741041024615577133971877), (54770579677621933410355416442876609320239324488267611540723693737657636078358, 5248524457624378021487642644172665678912203037724654722246208811322298201759), (64010856104962396238530175301346671588434668518585140706338242516095286450841, 77950702768338675364040935714359905411989011644919250301391768691105768409108)]
bb = [(4, 2333), (4, 5657), (6, 499), (7, 1103), (9, 10903), (11, 719), (14, 853), (14, 1567), (19, 1373), (20, 431), (21, 661), (23, 1291), (26, 8191), (28, 467), (30, 6073), (32, 2281), (32, 9241), (36, 487), (37, 4513), (42, 4621), (44, 439), (50, 14407), (53, 929), (55, 2729), (62, 617), (65, 25189), (65, 26099), (66, 881), (66, 1009), (73, 8117), (86, 10301), (91, 1693), (96, 2069), (98, 2357), (99, 14741), (100, 1663), (102, 1447), (106, 23929), (107, 953), (108, 16189), (109, 1783), (111, 13099), (112, 5527), (112, 2617), (117, 8737)]
primes = [i[1] for i in bb]
return Gs, bb, primes
def attack(s):
test = '0b' + ''.join(['1' for i in range(512)])
target = hex(int(test, 2))[2:]
Gs, bb, primes = init_all()
Exchange(s, Gs[0])
chioce(s, 'Encrypt', target)
deal_cipher(cipher[len(cipher) - 1], bb[0][1], Gs[0])
for i in range(1, len(Gs)):
chioce(s, 'Exchange', Gs[i])
chioce(s, 'Encrypt', target)
deal_cipher(cipher[len(cipher) - 1], bb[i][2], Gs[i])
ans_2 = CRT(primes, res)
ans = iroot(ans_2, 2)[0]
chioce(s, 'Backdoor', str(ans))
less1(s)
recvall(s)
attack(s)参考
Practical Invalid Curve Attacks on TLS-ECDH
