首页
社区
课程
招聘
[原创]密码风云部分关键源码
2018-12-31 10:33 9313

[原创]密码风云部分关键源码

2018-12-31 10:33
9313
说明:
其中Rotor加密可从相关的Python模块源码中获取,Skipjack算法对其F-Table进行了变换

整个题目涉及梅森素数、Hash算法、传统加密、对称算法、ECC公钥密码,总体思路如下:


1. 前面两个数都是梅森素数,即p是素数,2^p -1也是素数,对于10进制3位数,只有两个值,

这里为了降低难度,给出线索,在尝试出错10次以后,增加判断是否是素数的逻辑,便于判断这是梅森素数公式。

2. 计算两个梅森素数的和,并且计算转化为字符串之后的SM3哈希值,并简单计算Hash值的XOR校验值,如果校验通过,则用该Hash值作为Rotor算法的Key

3.对输入的Serial中间的24个字符数据进行解密,得到字符串cryptography,取其前10个字符,作为接下来Skipjack算法的密钥,对程序中

预存的24个字节进行解密,解密后的值为pediyctf2018.by.cnbragon,用于后面ECNR步骤的消息计算。这里对Skipjack的F-Table进行了变换。

4.使用同样的密钥,对serial的后面32个字符进行Skipjack解密,解密后的结果分别作为签名c和签名d

5.将字符串pediyctf2018.by.cnbragon以64位作为单位,进行xor,结果是ECNR的真正明文message

6.对签名c和签名d做ECNR签名验证,如果验证通过,为了保证serial的惟一并且进一步降低难度,增加了额外的加法校验



[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

最后于 2018-12-31 12:09 被kanxue编辑 ,原因:
上传的附件:
收藏
点赞2
打赏
分享
最新回复 (9)
雪    币: 28288
活跃值: (6706)
能力值: ( LV15,RANK:3306 )
在线值:
发帖
回帖
粉丝
风间仁 19 2018-12-31 14:28
2
1
这里的签名d要如何求解? d*G=R,(G,R已知, d最多60bit)

2019.01.02: 用 ecdlp_solver_by_mrhaandi 0.2A解(速度就是快, 0.3的暂时找不着了)
http://bbs.pediy.com/showthread.php?t=133058
最后于 2019-1-2 14:27 被风间仁编辑 ,原因:
雪    币: 3686
活跃值: (1036)
能力值: (RANK:760 )
在线值:
发帖
回帖
粉丝
cnbragon 18 2018-12-31 15:40
3
2
相信你已经求出c和i了,那么求d的话,有两种方法,第一种是根据P=dG + cW,求出点Q=P-cW=dG,求解该ECDLP得出d;
第二种是需要求两次ECDLP,
第一次是求u,知道了f,就等于知道了P,那么可以求出P=uG的ECDLP解
第二次是得出u以后,根据d = u-sc mod r求出d即可,其中s是私钥,即W=sG
了解了ECNR的公式即可明白
最后于 2018-12-31 16:13 被cnbragon编辑 ,原因:
雪    币: 28288
活跃值: (6706)
能力值: ( LV15,RANK:3306 )
在线值:
发帖
回帖
粉丝
风间仁 19 2018-12-31 17:16
4
1
这个求解d的python版本(mini_ecdsa)坑得很, 为免误导, 还是编辑掉
最后于 2019-1-2 14:30 被风间仁编辑 ,原因:
雪    币: 8188
活跃值: (4243)
能力值: ( LV15,RANK:2459 )
在线值:
发帖
回帖
粉丝
ccfer 16 2018-12-31 18:34
5
2
Initializing rho solver
k*G=K
G=[4091337503261587341,5999622034786369415]
K=[8772916103782998454,16434976567090442469]
Starting thread 0
Starting thread 2
Starting thread 3
Starting thread 4
Starting thread 7
Starting thread 1
Starting thread 6
Starting thread 5
Time for 10000000 steps: 1076
Time 63196ms; Steps: 1697600320; Points: 1605
k=3266752396307767
只有上面这组分解成功了

其它两种分解得到的结果都不正常
最后于 2018-12-31 18:41 被ccfer编辑 ,原因:
雪    币: 3686
活跃值: (1036)
能力值: (RANK:760 )
在线值:
发帖
回帖
粉丝
cnbragon 18 2018-12-31 20:37
6
1
给出正确的flag吧
10712763727970746f6772617068791c4cf9f6130f59f922985ad8f1e56bcc

如果没有得到正确结果,可以看问题是出在前面一部分验证,还是后面的ECNR验证,
前面几个验证( SM3、Rotor、Skipjack )应该都是比较常规的,可以对照flag自己做验证 
那我猜可能是ECNR计算时相关的一些中间点计算错了,
对于最后的ECNR校验,有几个地方要注意:
1. 要注意题目中验证的时候,有判断c的范围是在[1, r-1],这个千万别忽略了;
2. x坐标相同的情况下,会有两个点对应,要看清题目中设置的y坐标压缩位是0还是1,否则会导致你计算出来的点不对;
3. 最后的模加和模减,都是mod r的计算,这个一定要注意,否则也会得到不正确的结果。

首先给出正确的签名c和d的值如下:

c = 0x0456260d0e6c3ee1

d = 0x02e5addf9d20332d


进一步说明c的求解过程,在题目中很容易得到下面两个式子
f = c - i mod r =  0x5c6a9ef1f7a815c
m = c + i mod r  = 0x02e5a22afd5dfc66
求c的话,可以计算
f+m mod r = 0x8ac4c1a1cd87dc2,由于结果小于r,直接除以2就可以得到c的值

求d的过程上面描述过了,

下面是几个求ECDLP的结果,

求u的
Initializing ecdlp solver server
G: [4091337503261587341,5999622034786369415,1]
K: [7809717766337937581,12432779734384867297,1]
Time: +9 seconds, Relations: 669
Finalizing ecdlp solver server
The solution is: 49669979750137093
press enter to exit

求s的,
Initializing ecdlp solver server
G: [4091337503261587341,5999622034786369415,1]
K: [8772916103782998454,16434976567090442469,1]
Time: +6 seconds, Relations: 382
Finalizing ecdlp solver server
The solution is: 3266752396307767
press enter to exit

求签名d的
Initializing ecdlp solver server
G: [4091337503261587341,5999622034786369415,1]
K: [7639025867164727538,9357966862574065217,1]
Time: +20 seconds, Relations: 1645
Finalizing ecdlp solver server
The solution is: 208764133668041517
最后于 2018-12-31 21:58 被cnbragon编辑 ,原因:
雪    币: 10845
活跃值: (1049)
能力值: (RANK:190 )
在线值:
发帖
回帖
粉丝
看场雪 3 2018-12-31 21:07
7
1
风间仁 之前求解d用的是"Pollard's rho algorithm", 跑了6个小时没跑出来正常情况多久可以算出d?https://github.com/qubd/mini_ecds ...
pollard rho对空间要求不高
但如果能用BSGS用空间换取时间 则可以大幅缩短搜索时间
60bit的空间太大 不能采用默认的BS。只能根据实际内存量力而行
最后于 2018-12-31 21:41 被看场雪编辑 ,原因:
雪    币: 8188
活跃值: (4243)
能力值: ( LV15,RANK:2459 )
在线值:
发帖
回帖
粉丝
ccfer 16 2019-1-1 09:34
8
2
我知道问题在哪了,求d的时候有6个点满足在曲线上,我只随机试了其中3个点,刚好运气差没选对,剩下的3个点里有两个都可以得到解
所以还有第二组解也成立:
c = 0456260D0E6C3EE1
d = 0184C0B4E71C3923

k*G=K
G=[4091337503261587341,5999622034786369415]
K=[14080109935451529277,7817760537824282171]
Starting thread 0
Starting thread 3
Starting thread 1
Starting thread 2
Starting thread 4
Starting thread 5
Starting thread 6
Starting thread 7
Time for 10000000 steps: 421
Time 49733ms; Steps: 2079761280; Points: 1887
k=109424174167767331
雪    币: 28288
活跃值: (6706)
能力值: ( LV15,RANK:3306 )
在线值:
发帖
回帖
粉丝
风间仁 19 2019-1-1 15:13
9
0
忘记了Skipjack解密是以前面的sn为key的, 忘记更新那个常量Point了
雪    币: 34
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
罗马没有门 2019-8-3 17:37
10
0
100RMB求个0.3a的ECDLP solver
游客
登录 | 注册 方可回帖
返回