Meenpwn-2017-crypto-writeup

Meenpwn-2017-crypto-writeup

Simpler than RSA?

题目

"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：

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.txt和pubkey.txt就不直接贴出来了。

思路

前期分析

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

n = 1235280093599323856390922798440377476467763531842392869674688408727824382702235317
g = 1110549711091392805024587195974719739929628997819528005374351081843256209971586072
h = 610466084395822279908554174354632326166097007218620288020807622478449585661028278

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

$$c = [(g^{m}\mod n)\times(h^{r}\mod n )]\mod n$$

可以推出：

$$c\equiv(g^{m}\times h^{r}) \mod n$$

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

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

p = 1057817919251064684989791981
q = 1103935256393984899021164397

引理

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

$$a^{n}\equiv 1\mod m$$

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

$$a^{φ(m)}\equiv 1\mod m$$

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

$$a^{n\times{q}+r}\equiv 1\mod m$$

又因为$ a^{n\times{q}}\equiv 1\mod m $（这是n的性质），所以有：

$$a^{r}\equiv 1\mod m$$

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

$$a^{q}\equiv 1\mod m$$

结论

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

所以：

$$φ(n) = φ(p^{2}) \times φ(q)$$

因为：

所以：

$$φ(p^{2}) = (p-1) \times (p^{2-1}) = (p-1) \times p$$ $$φ(q) = (q-1) \times (q^{1-1}) = q-1$$

所以对φ(n)，有如下等式成立：

$$φ(n) = p \times {(p-1)} \times {(q-1)}$$

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

所以有：

$$h^{(p-1)\times{(q-1)}}\equiv{1}\mod{n}$$

也即：

$$h^{(p-1)\times{(q-1)}\times{r}}\equiv{1^{r}}\mod{n}$$

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

$$c^{(p-1)\times(q-1)} \equiv g^{m \times (p-1) \times (q-1)} \mod n$$

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

exp

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

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