Gunakan Python untuk melaksanakan penyulitan dan penyahsulitan RSA

Saya melihat artikel Bahasa Inggeris semalam [1] yang menunjukkan cara menggunakan Python untuk melaksanakan algoritma RSA Logik kod adalah sama seperti artikel sebelumnya Memahami Algoritma RSA boleh membaca artikel Memahami Algoritma RSA , yang menerangkan apa itu RSA, prinsip matematik RSA, dan memberikan contoh mudah Ia boleh dikatakan sebagai artikel paling mudah untuk memahami RSA dalam Quanzhihu (ini datang dari komen pembaca).

Saya menjalankan kod yang disediakan dalam bahasa Inggeris dan mendapati ia tidak boleh menyulitkan bahasa Cina, jadi saya mengubah suai fungsi penyulitan dan penyahsulitan untuk menyokong penyulitan dan penyahsulitan bahasa Cina. Artikel hari ini akan berkongsi cara menggunakan Python untuk melaksanakan penyulitan dan proses penyahsulitan RSA untuk membantu anda mewujudkan pemahaman intuitif tentang RSA Algoritma penjanaan nombor perdana rawak dalam kod juga patut dipelajari.

0. Demonstrasi kesan

Mari kita lihat kesannya dahulu.

Teks asal: "Ada tahi lalat, tamatkan transaksi"

Cryptotext, yang tidak boleh dipecahkan sama sekali:

Selepas penyahsulitan:

Akaun awam kod lengkap "Python No. 7" boleh diperolehi dengan membalas "rsa".

1. Penjanaan pasangan kunci

Idea:

1) Cari secara rawak dua nombor perdana (nombor perdana) p dan q Lebih besar p dan q, lebih selamat Di sini kita memilih nombor perdana 1024-bit:

p = genprime(1024)
q = genprime(1024)

Proses pelaksanaan fungsi genprime() tidak akan dibincangkan terlebih dahulu.

2) Kira hasil mereka n = p * q dan fungsi Euler lambda_n.

n = p * q
lambda_n = (p - 1) * (q - 1)

3) Pilih integer e secara rawak, dengan syarat 1 < e < lambda_n, dan e serta lambda_n adalah relatif utama. Contohnya, jika anda memilih 35537, 35537 hanya mempunyai 16 bit dan mestilah lebih kecil daripada lambda_n. < e < lambda_n，且 e 与 lambda_n 互质。比如选择 35537，35537 只有 16 位，必然小于 lambda_n。

e = 35537

4) Cari integer d supaya baki e * d dibahagikan dengan lambda_n ialah 1, dan kembalikan pasangan kunci.

d = eucalg(e, lambda_n)[0]
if d < 0: d += lambda_n
return (d, n), (e, n)

Perlaksanaan fungsi eucalg akan dibincangkan kemudian.

Pada ketika ini, fungsi penjanaan pasangan kunci adalah seperti berikut:

def create_keys():
 p = genprime(1024)
 q = genprime(1024)
 n = p * q
 lambda_n = (p - 1) * (q - 1)
 e = 35537
 d = eucalg(e, lambda_n)[0]
 if d < 0: d += lambda_n
 return (d, n), (e, n)

2 Pelaksanaan penyulitan dan penyahsulitan

Proses penyulitan dan penyahsulitan adalah sama. , penyulitan kunci awam , Penyahsulitan kunci persendirian, dan sebaliknya, penyulitan kunci persendirian dan penyahsulitan kunci awam, tetapi yang pertama dipanggil penyulitan dan yang terakhir dipanggil tandatangan.

Pelaksanaan fungsi khusus adalah seperti berikut:

def encrypt_data(data,key):
e_data = []
for d in data:
 e = modpow(d, key[0], key[1]) 
 e_data.append(e)
return e_data

## 加密和解密的逻辑完全一样
decrypt_data = encrypt_data

Fungsi modpow digunakan di sini, yang digunakan untuk mengira formula b^e % n = r.

• Jika ia adalah proses penyulitan, maka b ialah teks biasa, (n, e) ialah kunci awam, dan r ialah teks sifir.
• Jika ia adalah proses penyahsulitan, maka b ialah teks sifir, (n, d) ialah kunci persendirian, dan r ialah teks yang terkenal.

modpow ditakrifkan seperti berikut:

def modpow(b, e, n):
 # find length of e in bits
 tst = 1
 siz = 0
 while e >= tst:
tst <<= 1
siz += 1
 siz -= 1
 # calculate the result
 r = 1
 for i in range(siz, -1, -1):
r = (r * r) % n
if (e >> i) & 1: r = (r * b) % n
 return r

3. Fungsi penjanaan nombor perdana rawak

Fungsi penjanaan nombor perdana rawak, yang menggunakan pendaraban matriks dan Fibo Urutan itu menunjukkan kepentingan matematik kepada algoritma.

# matrix multiplication
def sqmatrixmul(m1, m2, w, mod):
 mr = [[0 for j in range(w)] for i in range(w)]
 for i in range(w):
for j in range(w):
 for k in range(w):
mr[i][j] = (mr[i][j] + m1[i][k] * m2[k][j]) % mod
 return mr

# fibonacci calculator
def fib(x, mod):
 if x < 3: return 1
 x -= 2
 # find length of e in bits
 tst = 1
 siz = 0
 while x >= tst:
tst <<= 1
siz += 1
 siz -= 1
 # calculate the matrix
 fm = [
# function matrix
[0, 1],
[1, 1]
 ]
 rm = [
# result matrix
# (identity)
[1, 0],
[0, 1]
 ]
 for i in range(siz, -1, -1):
rm = sqmatrixmul(rm, rm, 2, mod)
if (x >> i) & 1:
 rm = sqmatrixmul(rm, fm, 2, mod)

 # second row of resulting vector is result
 return (rm[1][0] + rm[1][1]) % mod

def genprime(siz):
 while True:
num = (1 << (siz - 1)) + secrets.randbits(siz - 1) - 10;
# num must be 3 or 7 (mod 10)
num -= num % 10
num += 3 # 3 (mod 10)
# heuristic test
if modpow(2, num - 1, num) == 1 and fib(num + 1, num) == 0:
 return num
num += 5 # 7 (mod 10)
# heuristic test
if modpow(2, num - 1, num) == 1 and fib(num + 1, num) == 0:
 return num

4. Pelaksanaan fungsi eucalg

Intipati fungsi adalah untuk mencari penyelesaian kepada persamaan linear berikut bagi dua pembolehubah:

e * x - lambda_n * y =1

Spesifik kod:

def eucalg(a, b):
 # make a the bigger one and b the lesser one
 swapped = False
 if a < b:
a, b = b, a
swapped = True
 # ca and cb store current a and b in form of
 # coefficients with initial a and b
 # a' = ca[0] * a + ca[1] * b
 # b' = cb[0] * a + cb[1] * b
 ca = (1, 0)
 cb = (0, 1)
 while b != 0:
# k denotes how many times number b
# can be substracted from a
k = a // b
# swap a and b so b is always the lesser one
a, b, ca, cb = b, a-b*k, cb, (ca[0]-k*cb[0], ca[1]-k*cb[1])
 if swapped:
return (ca[1], ca[0])
 else:
return ca

5. Ujian

kaedah penggunaan skrip test.py:

1), jana kunci

python test.py make-keys rsakey

Kunci awam disimpan dalam rsakey.pub , kunci peribadi disimpan dalam rsakey.priv

2), menyulitkan kandungan fail

Jika terdapat plaintext fail .txt:

python test.py encrypt 明文.txt from rsakey to 密文.txt

akan menjana ciphertext .txt

3 Nyahsulit kandungan fail

Jika terdapat ciphertext.txt:

python test.py decrypt 密文.txt as rsakey to 解密后.txt

. .txt yang dinyahsulit akan menjadi. dihasilkan

Perkataan akhir

Artikel ini berkongsi pelaksanaan mudah algoritma RSA dalam Python, yang boleh membantu memahami algoritma RSA.

Atas ialah kandungan terperinci Gunakan Python untuk melaksanakan penyulitan dan penyahsulitan RSA. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!