首页
社区
课程
招聘
[原创]KCTF2020春季赛题目(守株待兔) readyu 设计思路
发表于: 2020-4-12 23:19 8395

[原创]KCTF2020春季赛题目(守株待兔) readyu 设计思路

2020-4-12 23:19
8395

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


[招生]科锐逆向工程师培训(2024年11月15日实地,远程教学同时开班, 第51期)

最后于 2020-5-14 09:54 被readyu编辑 ,原因:
上传的附件:
收藏
免费 3
支持
分享
最新回复 (1)
雪    币: 195
能力值: ( LV4,RANK:57 )
在线值:
发帖
回帖
粉丝
2
推出了椭圆曲线了。。。不知道那个周期 只能瞎猜各种公式 就是没试(p+1)*(q+1)
2020-5-11 15:39
0
游客
登录 | 注册 方可回帖
返回
//