KCTF2020春季赛题目
设计思路
作者:readyu
说明:密码学题目, VC++ 编译的Win32程序。
#1 序列号(flag)
这个程序默认只有一个SN,用户名内置为username。输入正确的SN提示good work,错误的SN提示bad code。 本题唯一序列号(SN)为一整行字符串: flag{username-27D9A3DACA0B408853CBB1D79393864648F4DEA917066285C182C8B717A6822D9B67A541F173F75DB88-12C1975E404FA3E9356E6492BC2934E889F63FE98B623B83770CCFE519EFD5A9F5D0C1DB43A0F61D2BF} 就题目本身而言,本题是一个把椭圆曲线上和RSA结合来的公钥签名算法,简称KMOV。 格式为 :flag{name-X-Y} X,Y 都是大写字母的hex digit number,非0开头,每个name对应有1个key。 X-Y 是(name,hash) 的KMOV签名(公钥是小指数0x101,也就是257)。 这里用到的hash是 hmac_sha256(key,name), key是modulus N,在题目中,是椭圆曲线的模:一个10进制字符串。 彩蛋(额外赠送的)进入方式: (a) SN验证通过,再点击2下,可进入解锁模式,可针对不同的用户名验证SN。 (b) SN框内输入11个字符,点击check: ////debugme
#2 算法模型与解题分析
2.1 KMOV算法:在模N的椭圆曲线上实现RSA 本题实现了一个模N椭圆曲线上的RSA签名算法,算法名称是KMOV,(可以类比2019 Q3 模N的lucas序列上的RSA)。 算法的原始提出者是4个人,名字缩写是KMOV,论文简称为KMOV91: 《New Public-Key Schemes Based on Elliptic Curves over the Ring Zn》
Kenji Koyama , Ueli M. Maurer , Tatsuaki Okamoto , Scott A. Vanstone
说明:本题只用到这篇文章前5页的内容(6-13页不涉及到)。
这个算法模型,和传统的RSA可以对应,N是模,e是公钥,d是私钥,消息与签名编译为椭圆曲线的坐标x,y:
签名: R(x,y) = d * G(x,y) mod N 验证:
G(x,y) = e * R(x,y) mod N
其中:N = p * q, p, q是两个素数, 且 p, q = 2 mod 3 。 用到椭圆曲线的一个定理,如下的特殊椭圆曲线,a = 0: y^2 = x^3 + ax + b mod n 特殊地a = 0: y^2 = x^3 + b mod n
它的周期是,欧拉phi函数: phi = (p+1)*(q+1) , 这个phi的含义类似RSA里面的(p-1)*(q-1)。
d是私钥(大指数), e是公钥(小指数,可以取一个小素数,与phi互素的,比如257, 63357),
对应地,有 e*d = 1 mod phi
所以就可以把RSA的原理应用到模n的椭圆曲线上(n是一个rsa number,注意不是模p,或者模q)。 2.2 题目验证流程
step 1:
从flag{username-X-Y} 里提取username, X, Y
题目用到:modulus=
"1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139" 如下处理: msg = "KXCTF2020.readyu.Catch.Rabbit:username" 然后取key=modulus 字符串,计算: hash = hmac_sha256(key, msg) 我们有: h = hmac_sha256(key, msg)=77C13E81BEACB06B6D544BDFCA684BB07F6939D887CEC1AFCE2CA10E099A1C58 h是32字节长度,然后在h前面固定地加上一个字节0x21(10进制为33).
hash = 2177C13E81BEACB06B6D544BDFCA684BB07F6939D887CEC1AFCE2CA10E099A1C58
step 2: X,Y 作为椭圆曲线的坐标输入, R(X,Y), 计算 G(X,Y) = 257 * R(X,Y)
椭圆曲线的加法是这么计算的: y^2 = x^3 + a*x + b add point: (x3,y3) = (x1,y1) + (x2, y2) k = (y2 - y1)/(x2-x1) x3 = k*k - x1 - x2 y3 = k*(x1 - x3) - y1 double point: (x3,y3) = (x1,y1) + (x1,y1) k = (3*x1*x1+a)/2*y1 x3 = k*k - x1 - x1 y3 = k*(x1 - x3) - y1 由于在题目里,e取257 = 2^8+1, 所以题目只实现一个小指数乘法 e*R(x,y) 。 椭圆曲线的基本运算是加法,题目就是用了8次double, 1次add。 G(X,Y) = 257 * R(X,Y) ,因为:257 = 2*2^7 + 1 所以: G = 2^7*(R+R) + R static void encrypt_e(Big &x1, Big &y1, Big &n) { int i; Big x2, y2, k; // 0x101 = 2^8 + 1 // (x2, y2) = 2*(x1,y1) y2 = 3*x1*x1; x2 = 2*y1; k = inverse(x2, n); k *= y2; x2 = (k*k - x1 - x1) % n; y2 = (k*(x1 - x2) - y1) % n; // 2^7 * (x2,y2) for(i = 0; i < 7; i++) dbl_point(x2, y2, x2, y2, n); add_point(x2, y2, x1, y1, n); return; } step 3: 验证X,Y坐标分别是对应的签名: X坐标: G.X = msg, 题目里其实是验证 hmac_sha256(modulus, G.X) = hmac_sha256(modulus, msg) Y坐标: G.Y = hash 2.3 解题的Keygen流程:
step1:
modulus.key=
1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 msg=KXCTF2020.readyu.Catch.Rabbit:username
hash=hmac_sha256(key, msg)=77C13E81BEACB06B6D544BDFCA684BB07F6939D887CEC1AFCE2CA10E099A1C58
如下生成G点坐标:
G.x = msg.bytes, G.y = 0x21 || hash,
那么:
G(x,y)= 4B58435446323032302E7265616479752E43617463682E5261626269743A757365726E616D65
2177C13E81BEACB06B6D544BDFCA684BB07F6939D887CEC1AFCE2CA10E099A1C58
step 2:
计算:n = p*q (这个RSA-100是公开的)
RSA-100 = 37975227936943673922808872755445627854565536638199 * 40094690950920881030683735292761468389214899724061 e = 257 计算 phi = (p+1)*(q+1), 计算 d = e^-1 mod phi
step 3:
计算 R=d*G(x,y)=
27D9A3DACA0B408853CBB1D79393864648F4DEA917066285C182C8B717A6822D9B67A541F173F75DB88 12C1975E404FA3E9356E6492BC2934E889F63FE98B623B83770CCFE519EFD5A9F5D0C1DB43A0F61D2BF 同时我们可以验证: G(x,y)=e*R(x,y)= 4B58435446323032302E7265616479752E43617463682E5261626269743A757365726E616D65 2177C13E81BEACB06B6D544BDFCA684BB07F6939D887CEC1AFCE2CA10E099A1C58 可见X坐标是msg的字符串,而Y坐标是hash字符串。 G(x).str=KXCTF2020.readyu.Catch.Rabbit:username 于是,符合username的flag为: flag{username-27D9A3DACA0B408853CBB1D79393864648F4DEA917066285C182C8B717A6822D9B67A541F173F75DB88-12C1975E404FA3E9356E6492BC2934E889F63FE98B623B83770CCFE519EFD5A9F5D0C1DB43A0F61D2BF}
#3 keygen源代码:
附件keygen源代码 keygenme2020q1_kmov_keygen ,VC++6 测试通过。 crackme只用到椭圆曲线的点加 , 而keygen要用到k倍加(点乘, R = k* G), 所以要实现mul算法,参见源代码。 这里同样给出keygen的源代码,点加的方法和之前2019Q4的题目Edwards curve椭圆曲线类似。 但是本题椭圆曲线是最基本的类型,没有射影坐标变换,所以简单一些。 keygen用的是二进制展开法,这个方法最便于理解, k的展开如下描述: // x2,y2 = k* x1,y1 // k = base2 : an | an-1 | ... | a1 | a0, ai = (0, 1) // k = a0 + 2 * a1 + 4*a2 +...+ 2^n*an 上传的附件:
阿里云助力开发者!2核2G 3M带宽不限流量!6.18限时价,开
发者可享99元/年,续费同价!
最后于 2020-5-14 09:54
被readyu编辑
,原因:
上传的附件: