一.Paillier加密

介绍

Paillier加密系统，是1999年Paillier发明的概率公钥加密系统。基于复合剩余类的困难问题。该加密算法是一种同态加密，满足加法和乘法同态。

1 秘钥生成

xbfBuj.png

2 加密

xbfDDs.png

3.解密

xbfrbn.png

例题

[DASCTF 2020 四月春季赛] not_RSA

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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=%d"%(c)
print "n=%d"%(n)

c=29088911054711509252215615231015162998042579425917914434962376243477176757448053722602422672251758332052330100944900171067962180230120924963561223495629695702541446456981441239486190458125750543542379899722558637306740763104274377031599875275807723323394379557227060332005571272240560453811389162371812183549
n=6401013954612445818165507289870580041358569258817613282142852881965884799988941535910939664068503367303343695466899335792545332690862283029809823423608093

exp1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import long_to_bytes,bytes_to_long
import gmpy2

p = gmpy2.mpz(80006336965345725157774618059504992841841040207998249416678435780577798937819)
q = gmpy2.mpz(80006336965345725157774618059504992841841040207998249416678435780577798937447)
n = gmpy2.mpz(6401013954612445818165507289870580041358569258817613282142852881965884799988941535910939664068503367303343695466899335792545332690862283029809823423608093)
c = gmpy2.mpz(29088911054711509252215615231015162998042579425917914434962376243477176757448053722602422672251758332052330100944900171067962180230120924963561223495629695702541446456981441239486190458125750543542379899722558637306740763104274377031599875275807723323394379557227060332005571272240560453811389162371812183549)

phi = (p-1)*(q-1)
u = gmpy2.invert(phi,n)

def L(x):
	return (x-1)//n

b = gmpy2.powmod(c,phi,n*n)

m = (L(b)*u) % n
flag = long_to_bytes(m)

print(flag)

exp2：

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *

p = 80006336965345725157774618059504992841841040207998249416678435780577798937819
q = 80006336965345725157774618059504992841841040207998249416678435780577798937447
n = p * q
c = 29088911054711509252215615231015162998042579425917914434962376243477176757448053722602422672251758332052330100944900171067962180230120924963561223495629695702541446456981441239486190458125750543542379899722558637306740763104274377031599875275807723323394379557227060332005571272240560453811389162371812183549
lcm = ((p - 1) * (q - 1)) // GCD(p - 1, q - 1)
a = (pow(c, lcm, n * n) - 1) // n
b = (pow(n + 1, lcm, n * n) - 1) // n
m = long_to_bytes((a * inverse(b, n)) % n)
print(m)

二.密钥交换技术

1.DHE: Diffie–Hellman key exchange

加密协议

xbWItf.png

安全性体现在大数p时的离散对数难以求解x和y上。

离散对数求解

对于给定 c = m ^ （flag) % n

flag = discrete_log（c,n,m）

求离散对数（如下7 ^ 3mod15=41）：

1
discrete_log(41, 15, 7)

使用案例：（buuctf newstar week3）

加密key：

1
2
3
from secret import flag, gb, g, p, Diffie_Hellman_KEY_EXCHANGE
shared = Diffie_Hellman_KEY_EXCHANGE(a) 
key = md5(str(shared).encode()).digest()

解密key：

pyDHE是一款采用Python语言开发的工具，它完整地实现了Diffie-Hellman算法。

1
2
3
4
5
6
7
8
9
10
import pyDHE
d1 = pyDHE.new()
d1.g = ?
d1.p = ?
d1.a = ? (secret key)
d1.group()
d2 = ? (public key)
d1.update(d2)
shared = d1.getFinalKey()
key = md5(str(shared).encode()).digest()

2.ECDHE:（基于椭圆曲线）

小红和小明使用 ECDHE 密钥交换算法的过程：

  • 双方事先确定好使用哪种椭圆曲线，和曲线上的基点 G，这两个参数都是公开的；
  • 双方各自随机生成一个随机数作为私钥d，并与基点 G相乘得到公钥Q（Q = dG），此时小红的公私钥为 Q1 和 d1，小明的公私钥为 Q2 和 d2；
  • 双方交换各自的公钥，最后小红计算点（x1，y1） = d1Q2，小明计算点（x2，y2） = d2Q1，由于椭圆曲线上是可以满足乘法交换和结合律，所以 d1Q2 = d1d2G = d2d1G = d2Q1 ，因此双方的 x 坐标是一样的，所以它是共享密钥，也就是会话密钥。

例题：buuctf newstar week5

题目：

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
from secret import FLAG, ECDH_KEY_EXCHANGE
from Crypto.Cipher import AES
from hashlib import md5
from os import urandom

iv = urandom(16)


a = 14489
b = 10289
p = 7486573182795736771889604737751889118967735916352298289975055815020934891723453392369540853603360270847848895677903334441530052977221688450741083448029661

F = GF(p)
E = EllipticCurve(F, [a, b])

G = E.random_point()

my_private_key = random_prime(2^256)

shared, sender_public_key = ECDH_KEY_EXCHANGE(G, my_private_key)

key = md5(str(int(shared.xy()[0])).encode()).digest()

cipher = AES.new(key, AES.MODE_CBC, iv)
ciphretext = cipher.encrypt(FLAG)

print(a)
print(b)
print(p)
print(sender_public_key)
print(my_private_key)
print(ciphretext.hex())
print(iv.hex())

这是一道ECDHE的密钥交换，分析task文件，发现采用ECDHE协议，my_private_key表示某个私钥a（假定为用户A的私钥），sender_public_key 为交换的公钥 b* G(B用户加密后生成的)，不难发现用my_private_key * sender_public_key 即为公共密钥shared：

a * b * G，通过shared进而可以获取key，之后就是常规aes。

exp：

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
from Crypto.Cipher import AES
from hashlib import md5
from libnum import n2s,s2n
from os import urandom
import binascii
#用sagemath运行代码
a = 14489
b = 10289
p =7486573182795736771889604737751889118967735916352298289975055815020934891723453392369540853603360270847848895677903334441530052977221688450741083448029661
F= GF(p)
E=EllipticCurve(F,[a,b])
sender_public_key=E([1285788649714386836892440333012889444698233333809489364474616947934542770724999997145538088456652601147045234490019282952264340541239682982255115303711207,           1081635450946385063319483423983665253792071829707039194609541132041775615770167048603029155228167113450196436786905820356216200242445665942628721193713459])
my_private_key = 2549545681219766023689977461986014915946503806253877534915175093306317852773
shared =sender_public_key*my_private_key
key = md5(str(int(shared.xy () [0]) ).encode()).digest()
print(key)
#key = b"\xbe\xf7\x1d\x06\xa8\xd1\xeb\xa2\xfa7\xf3\x87q'H."               //以上代码需要sagemath运行。

iv = 0xd151c04c645c3e2a8d3f1ae44589ef20
ciphretext = 0x2f65ff4a97e0e05c06eab06b58ea38a3d5b6d2a65ea4907bc46493b30081a211d7cffc872a23dbd565ef307f9492bb23
iv = n2s(iv)
ciphretext = n2s((ciphretext))
cipher = AES.new(key,AES.MODE_CBC,iv)
flag = cipher.decrypt(ciphretext)
print(flag)

#b'flag{ell1ptic_curv3_i5_be4ut1ful_right#4DF17ABE}'

Pill方程

求解：a^2−d * b^2 = 1

exp：

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
import numpy as np
from collections import deque

d = xxxxxx             
m = int(np.sqrt(d))
dq = deque()
dq.append(m)
n0 = n1 = d - m * m
m1 = m
while 1:
    q, m2 = divmod(m1 + m, n1)
    dq.appendleft(q)
    m1 = -m2+m
    n1 = (d-m1*m1)//n1
    if m1 == m and n1 == n0:
        break

dq.popleft()
x = 1
y = 0
for i in dq:
    x1 = y + x * i
    y = x
    x = x1
    y1=y
if x*x-d*y*y==-1:
   b=(x**2+d*y**2)
   y1=2*x*y
   x1=b
print('x1=',x1)
print('y1=',y1)