# Learn Paillier crytposystem from "not_RSA" in DASCTF

## “not_RSA” in DASCTF

  1 2 3 4 5 6 7 8 9 10 11 12 13 14  from Crypto.Util.number import getPrime as getprime ,long_to_bytes,bytes_to_long,inverse from secret import flag,p,q from sympy import isprime,nextprime import random m=bytes_to_long(flag) n=p*q g=n+1 r=random.randint(1,n) c=(pow(g,m,n*n)*pow(r,n,n*n))%(n*n) print('c=',c) print('n=',n) 

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38  from Crypto.Util.number import long_to_bytes, inverse from functools import reduce c = 29088911054711509252215615231015162998042579425917914434962376243477176757448053722602422672251758332052330100944900171067962180230120924963561223495629695702541446456981441239486190458125750543542379899722558637306740763104274377031599875275807723323394379557227060332005571272240560453811389162371812183549 n = 6401013954612445818165507289870580041358569258817613282142852881965884799988941535910939664068503367303343695466899335792545332690862283029809823423608093 p = 80006336965345725157774618059504992841841040207998249416678435780577798937819 q = 80006336965345725157774618059504992841841040207998249416678435780577798937447 g = n+1 phi = (p-1)*(q-1) rn = c % n x1 = rn % p d1 = inverse(q, p-1) r1 = pow(x1, d1, p) x2 = rn % q d2 = inverse(p, q-1) r2 = pow(x2, d2, q) def CRT(m, a): Num = len(m) M = reduce(lambda x, y: x*y, m) Mi = [M//i for i in m] t = [inverse(Mi[i], m[i]) for i in range(Num)] x = 0 for i in range(Num): x += a[i]*t[i]*Mi[i] return x % M r = CRT([p, q], [r1, r2]) R = pow(r, n, n*n) R_inv = inverse(R, n*n) mn = (c*R_inv) % (n*n) m = (mn-1)//n print(long_to_bytes(m)) 

## Paillier Crytposystem

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40  from Crypto.Util.number import* from gmpy2 import lcm class Paillier(): def __init__(self): pass def encrypt(self, m): p, q = getPrime(512), getPrime(512) n = p*q self.n = n assert m < n Lcm = lcm(p-1, q-1) g = getRandomRange(1, n*n) while GCD(self.L(pow(g, Lcm, n*n)), n) != 1: g = getRandomRange(1, n*n) r = getRandomRange(1, n) return (pow(g, m, n*n)*pow(r, n, n*n)) % (n*n), p, q, g def decrypt(self, c, p, q, g): n = p*q assert c < n*n Lcm = lcm(p-1, q-1) self.n = n self.d = inverse((p-1)*(q-1), n) m_c = self.L(pow(c, Lcm, n*n)) m_g = self.L(pow(g, Lcm, n*n)) m = m_c*inverse(m_g, n) % n return m def L(self, u): return (u-1)//self.n m = bytes_to_long(b'flag{1234567890}') P = Paillier() c, p, q, g = P.encrypt(m) M = P.decrypt(c, p, q, g) print(long_to_bytes(M)) # b'flag{1234567890}' 

exp:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19  from Crypto.Util.number import long_to_bytes,inverse from gmpy2 import lcm c = 29088911054711509252215615231015162998042579425917914434962376243477176757448053722602422672251758332052330100944900171067962180230120924963561223495629695702541446456981441239486190458125750543542379899722558637306740763104274377031599875275807723323394379557227060332005571272240560453811389162371812183549 n = 6401013954612445818165507289870580041358569258817613282142852881965884799988941535910939664068503367303343695466899335792545332690862283029809823423608093 p = 80006336965345725157774618059504992841841040207998249416678435780577798937819 q = 80006336965345725157774618059504992841841040207998249416678435780577798937447 g = n+1 phi = (p-1)*(q-1) def decrypt(c, p, q, g): n = p*q Lcm = lcm(p-1, q-1) m_c = (pow(c, Lcm, n*n)-1)//n m_g = (pow(g, Lcm, n*n)-1)//n m = m_c*inverse(m_g, n) % n return m m=decrypt(c, p, q, g) print(long_to_bytes(m)) #b'flag{5785203dbe6e8fd8bdbab860f5718155}'