Chybeta

Meenpwn-2017-crypto-writeup

Meenpwn-2017-crypto-writeup

Simpler than RSA?

题目

1
2
"RSA is just math". And now, there is a cryptosystem that simpler than RSA, but, "Simple is the Best!"
simple.py pubkey.txt enc.txt

simple.py:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
import random
from flag import FLAG
def generate(nbits):
p = getPrime(nbits)
q = getPrime(nbits)
n = p * q * p
g = random.randint(1, n)
h = pow(g, n, n)
return (n, g, h)
def encrypt(m, n, g, h):
r = random.randint(1, n)
c = pow(pow(g, m, n) * pow(h, r, n), 1, n)
return c
m = [ord(char) for char in FLAG]
n, g, h = generate(90)
open("pubkey.txt", "w").write("{0}:{1}:{2}".format(n, g, h))
c = [encrypt(mi, n, g, h) for mi in m]
open("enc.txt", "w").write(str(c))

enc.txtpubkey.txt就不直接贴出来了。

思路

前期分析

先对题目进行一下分析。目前已知

1
2
3
n = 1235280093599323856390922798440377476467763531842392869674688408727824382702235317
g = 1110549711091392805024587195974719739929628997819528005374351081843256209971586072
h = 610466084395822279908554174354632326166097007218620288020807622478449585661028278

密文c也已知。由simply.py知道:

可以推出:

其中的r是未知的,我们要想办法消去它。

继续分析。n = p q p,其中q,p均为质数,拿到factordb上分解出:

1
2
p = 1057817919251064684989791981
q = 1103935256393984899021164397

引理

参考:The smallest solution of a^x = 1 mod m with (a,m) = 1,这边简要记录。
假设正整数n是满足下列同余式的最小正整数,并且a和m互质:

由欧拉定理,有如下同余式。其中φ(m)是m的欧拉函数,表示小于m的与m互质的正整数的个数。

现在假设$φ(m)=n\times{q}+r$,其中n的意义同上,q为商,r为余数。则欧拉定理可以改写为:

又因为$ a^{n\times{q}}\equiv 1\mod m $(这是n的性质),所以有:

因为r<n,而n是使同余式成立的最小正整数,所以必有r=0。所以接下去推导有:

结论

回到本题中,$n={p}^{2}\times{q}$,接下来我们考虑n的欧拉函数φ(n)
因为:

所以:

因为:

所以:

所以对φ(n),有如下等式成立:

我们想要消去r,所以对h进行考虑,h和n互质,现在我们要找到φ(n)的一个分解因子k,使得根据引理,有$h^{k} \equiv 1 \mod n$。选择k=(p-1)*(q-1)恰好满足。

所以有:

也即:

在$ c\equiv(g^{m}\times h^{r}) \mod n $同时加上(p-1)*(q-1)次方。可以推得:

其中m是明文的每一个字符,是可显的,范围为从32~126。可以对其进行爆破。

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = 1235280093599323856390922798440377476467763531842392869674688408727824382702235317
g = 1110549711091392805024587195974719739929628997819528005374351081843256209971586072
h = 610466084395822279908554174354632326166097007218620288020807622478449585661028278
p = 1057817919251064684989791981
q = 1103935256393984899021164397
tphi = (p-1)*(q-1)
ciper = [...太长省略...]
flag = ''
for c in ciper:
temp = pow(c,tphi,n)
for f in range(32,127):
if temp == pow(g,f*tphi,n):
flag += chr(f)
print(flag)

题目涉及文件:链接:http://pan.baidu.com/s/1qYTsJjY 密码:rnw7

nub_cryptosystem

1
2
Quan is a nub-boi at Cryptography, but his dream is having an unbreakable cryptosystem. Could you prove him that "nub is always nub" by breaking his 'nub_cryptosystem'?
nub_cryptosystem.py pubkey.txt enc.txt

justpad

|\/|/-\T|-|

Freedom Curve

点击赞赏二维码,您的支持将鼓励我继续创作!
chybeta WeChat Pay

微信打赏

chybeta Alipay

支付宝打赏

本文标题:Meenpwn-2017-crypto-writeup

文章作者:chybeta

发布时间:2017年07月19日 - 20:07

最后更新:2017年07月28日 - 15:07

原始链接:http://chybeta.github.io/2017/07/19/Meenpwn-2017-crypto-writeup/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。