RSA算法
RSA算法是一种公钥加密技术,被认为是最安全的加密方式.它是由Rivest,Shamir和Adleman于1978年发明的,因此命名为 RSA 算法.
RSA算法具有以下特征 :
- RSA算法是包含素数的整数在有限域中的一种流行取幂./p>
- 此方法使用的整数足够大,难以解决.
- 此算法中有两组密钥:私钥和公钥.
您必须完成以下步骤才能工作关于RSA算法 :
步骤1:生成RSA模数
初始过程从选择两个素数即p和q开始,然后计算他们的产品N,如图所示去;
N = p * q
这里,设N为指定的大数.
步骤2:派生数(e)
将数字e视为派生数,该数字应大于1且小于(p-1)和(q-1).主要条件是应该没有(p-1)和(q-1)的公因子,除了1
步骤3:公钥
指定的一对数字 n 和 e 形成RSA公钥并将其公开.
步骤4:私钥
私钥 d 是根据数字p,q和e计算的.数字之间的数学关系如下:
ed = 1 mod(p-1)(q-1)
上面的公式是扩展欧几里得算法的基本公式,它以p和q作为输入参数.
加密公式
考虑将明文消息发送给公钥为(n,e)的人的发件人.要在给定方案中加密纯文本消息,请使用以下语法 :
C = Pe mod n
解密公式
解密过程非常简单,包括用于系统方法计算的分析.考虑到接收器 C 具有私钥 d ,结果模数将计算为 :
Plaintext = Cd mod n
生成RSA密钥
我们将重点介绍使用Python逐步实现RSA算法.
涉及以下步骤生成RSA密钥 :
- 创建两个大的素数,即 p 和 q 的.这些数字的乘积称为 n ,其中 n = p * q
- 生成一个(p-1)和(q-1)相对素数的随机数.将数字称为 e .
- 计算e的模数逆.计算出的倒数将被称为 d .
生成RSA密钥的算法
我们需要两个主要算法来使用Python和minus生成RSA密钥; Cryptomath模块和 Rabin Miller模块.
Cryptomath模块
cryptomath的源代码遵循RSA算法的所有基本实现的模块如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
def gcd(a, b): while a != 0: a, b = b % a, a return b def findModInverse(a, m): if gcd(a, m) != 1: return None u1, u2, u3 = 1, 0, a v1, v2, v3 = 0, 1, m while v3 != 0: q = u3 // v3 v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3 return u1 % m |
RabinMiller模块
源代码遵循RSA算法的所有基本实现的RabinMiller模块如下<
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
41
42
43
44
|
import random def rabinMiller(num): s = num - 1 t = 0 while s % 2 = = 0 : s = s / / 2 t + = 1 for trials in range ( 5 ): a = random.randrange( 2 , num - 1 ) v = pow (a, s, num) if v ! = 1 : i = 0 while v ! = (num - 1 ): if i = = t - 1 : return False else : i = i + 1 v = (v * * 2 ) % num return True def isPrime(num): if (num 7 < 2 ): return False lowPrimes = [ 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 , 109 , 113 , 127 , 131 , 137 , 139 , 149 , 151 , 157 , 163 , 167 , 173 , 179 , 181 , 191 , 193 , 197 , 199 , 211 , 223 , 227 , 229 , 233 , 239 , 241 , 251 , 257 , 263 , 269 , 271 , 277 , 281 , 283 , 293 , 307 , 311 , 313 , 317 , 331 , 337 , 347 , 349 , 353 , 359 , 367 , 373 , 379 , 383 , 389 , 397 , 401 , 409 , 419 , 421 , 431 , 433 , 439 , 443 , 449 , 457 , 461 , 463 , 467 , 479 , 487 , 491 , 499 , 503 , 509 , 521 , 523 , 541 , 547 , 557 , 563 , 569 , 571 , 577 , 587 , 593 , 599 , 601 , 607 , 613 , 617 , 619 , 631 , 641 , 643 , 647 , 653 , 659 , 661 , 673 , 677 , 683 , 691 , 701 , 709 , 719 , 727 , 733 , 739 , 743 , 751 , 757 , 761 , 769 , 773 , 787 , 797 , 809 , 811 , 821 , 823 , 827 , 829 , 839 , 853 , 857 , 859 , 863 , 877 , 881 , 883 , 887 , 907 , 911 , 919 , 929 , 937 , 941 , 947 , 953 , 967 , 971 , 977 , 983 , 991 , 997 ] if num in lowPrimes: return True for prime in lowPrimes: if (num % prime = = 0 ): return False return rabinMiller(num) def generateLargePrime(keysize = 1024 ): while True : num = random.randrange( 2 * * (keysize - 1 ), 2 * * (keysize)) if isPrime(num): return num |
生成RSA密钥完整代码
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
41
42
43
44
45
46
47
48
49
50
|
import random, sys, os, rabinMiller, cryptomath def main(): makeKeyFiles( 'RSA_demo' , 1024 ) def generateKey(keySize): # Step 1: Create two prime numbers, p and q. Calculate n = p * q. print ( 'Generating p prime...' ) p = rabinMiller.generateLargePrime(keySize) print ( 'Generating q prime...' ) q = rabinMiller.generateLargePrime(keySize) n = p * q # Step 2: Create a number e that is relatively prime to (p-1)*(q-1). print ( 'Generating e that is relatively prime to (p-1)*(q-1)...' ) while True : e = random.randrange( 2 * * (keySize - 1 ), 2 * * (keySize)) if cryptomath.gcd(e, (p - 1 ) * (q - 1 )) = = 1 : break # Step 3: Calculate d, the mod inverse of e. print ( 'Calculating d that is mod inverse of e...' ) d = cryptomath.findModInverse(e, (p - 1 ) * (q - 1 )) publicKey = (n, e) privateKey = (n, d) print ( 'Public key:' , publicKey) print ( 'Private key:' , privateKey) return (publicKey, privateKey) def makeKeyFiles(name, keySize): # Creates two files 'x_pubkey.txt' and 'x_privkey.txt' (where x is the value in name) with the the n,e and d,e integers written in them, # delimited by a comma. if os.path.exists( '%s_pubkey.txt' % (name)) or os.path.exists( '%s_privkey.txt' % (name)): sys.exit( 'WARNING: The file %s_pubkey.txt or %s_privkey.txt already exists! Use a different name or delete these files and re-run this program.' % (name, name)) publicKey, privateKey = generateKey(keySize) print () print ( 'The public key is a %s and a %s digit number.' % ( len ( str (publicKey[ 0 ])), len ( str (publicKey[ 1 ])))) print ( 'Writing public key to file %s_pubkey.txt...' % (name)) fo = open ( '%s_pubkey.txt' % (name), 'w' ) fo.write( '%s,%s,%s' % (keySize, publicKey[ 0 ], publicKey[ 1 ])) fo.close() print () print ( 'The private key is a %s and a %s digit number.' % ( len ( str (publicKey[ 0 ])), len ( str (publicKey[ 1 ])))) print ( 'Writing private key to file %s_privkey.txt...' % (name)) fo = open ( '%s_privkey.txt' % (name), 'w' ) fo.write( '%s,%s,%s' % (keySize, privateKey[ 0 ], privateKey[ 1 ])) fo.close() # If makeRsaKeys.py is run (instead of imported as a module) call # the main() function. if __name__ = = '__main__' : main() |
输出
生成公钥和私钥并将其保存在相应的文件中,如以下输出所示.
以上就是python密码学RSA算法及秘钥创建教程的详细内容,更多关于python密码学RSA算法秘钥的资料请关注服务器之家其它相关文章!
原文链接:https://www.it1352.com/OnLineTutorial/cryptography_with_python/cryptography_with_python_understanding_rsa_algorithm.html