Golden Metal

Decription

Category: Crypto Points: 300 Solves: 21 Description:
The flag is encrypted by this code, can you decrypt it after finding the system?
https://github.com/ctfs/write-ups-2015/tree/master/asis-quals-ctf-2015/crypto/golden-metal
Status: Unsolved
Tag : Crypto, Asymmetric cryptography, Number theory, Math
Find me if you have questions: w.zongyu@gmail.com
Reference: https://github.com/ctfs/write-ups-2015/tree/master/asis-quals-ctf-2015/crypto/golden-metal

Solve

The file contains a cryptographic algorithm, a ciphertext and a public key. Our goal is to find out what is the message before encrypted.

The algorithm description is below:
First, generate N=pq.
N is 320 bit big number public key(Means we have this)
p,q is 160 bit big prime number secret key(Means we do not have this)
But (p+1)%4 = 0 and (q+1)%4 = 0

Second, find radix
Find X, such that
q^(p-1)*X^((q-1)/2) = p-1 (mod p)
p^(q-1)*X^((p-1)/2) = q-1 (mod q)
Considering Fermat little theorem
We can rewrite the formula to
X^((q-1)/2) = p-1 (mod p)
X^((p-1)/2) = q-1 (mod q)

Third, encrypt message
Generate random value y, GCD(y, N)==1
We transform message into binary A=0100 0001
When bit = 1, C = ((X^(2y+1))modN * y^2)modN
When bit = 0, C = ((X^(2y+0))modN * y^2)modN

The algorithm is Goldwasser–Micali (GM) cryptosystem
大致上把演算法了解後做一些筆記:
這個演算法是第一個非對稱式的加密方式,後來這兩位演算法的發明家也拿到的了Turing award。
GM密碼系統是利用給定一個X在modN(N=pq)環(Ring)下我們要知道**隨機**的X是否是quadratic residue是非常困難的(eg. find y^2 = x modN)
但是在modp有限體(Finite Field)之下要判斷隨機的X是否是quadratic residue是很容易的事情

GM algorithm的細節

Gnerating key
p=big prime
q=big prime
N=pq
Find x such that legendre symbol for x/p = x/q = (-1), so the Jacobi symbol for x/n = +1 = x/p * x/q.
選x的方式是用利用random並且測試, 或是在(p+1)%4 = 0 and (q+1)%4 = 0,也就是p與q是Bulm integer的狀況下p-1一定會符合需要的狀況(q的狀況亦然)
Public key: (X,N)
Private key: (p,q)

Encryption
y=RandInt(1,N) and gcd(y, N)=1

If m[i] = 0

=> not quartic residue
else if m[i] = 1

=> quartic residue

Decrypt
For each i, using the prime factorization (p, q), Alice determines whether the value ci is a quadratic residue; if so, mi = 0, otherwise mi = 1.

Ok, 大致上一樣而不太一樣的地方在於這個題目給的方式是((X^(2y+m[i]))modN * y^2)modN,而原先的演算法是C=(X^m[i] * y^2) modN,其實是用相同的性質,當m[i]=0時: ((X^(2y))mod * y^2)modN = (X^(2y) * y ^ 2)modN這也是一個quadratic residue
測試一個數是否為quadratic residue可以利用Euler's criterion

利用cado-nfs做N的質因數分解
Info:Complete Factorization: Total cpu/elapsed time for entire factorization: 7882.22/8429.37
1358902095093762824984385249873903079031552839163
1285380609783825451015579898011805465763518244839

if __name__ == "__main__":
d=eval(open("enc.txt").read()[5:])
p=1358902095093762824984385249873903079031552839163
ans=""
for a in d:
   if pow(a, (p-1)/2, p)==1:
       ans+="0"
   elif pow(a, (p-1)/2, p)==p-1:
       ans+="1"
  else:
      print 'error'

print ("%x"%int(ans, 2)).decode("hex")

ASIS{3c4cbc2d6bc6ebbbbbe967b8af5ac414}