Program : Textbook RSA (on group)
In this part, you are required to implement the textbook RSA algorithm from scratch. It contains the following three procedures, KeyGen, Encrypt, and Decrypt.
Your program does the following:
Note that in this program, you may only include third-party codes or libraries for:
- Miller-Rabin Test
- Extended Euclidean Algorithm
Recall that including any third-party codes without claiming is considered as lack of academic integrity, and results in failing this course.
Example Input & Output
Input:
代码语言：javascript复制34862844108815430278935886114814204661242105806196134451262421197958661737288465541172280522822644267285105893266043422314800759306377373320298160258654603531159702663926160107285223145666239673833817786345065431976764139550904726039902450456522584204556470321705267433321819673919640632299889369457498214445Output:
代码语言：javascript复制Private key:
N: 72480887416135972061737686062889407161759160887103574047817069443537714713215543172947835307344891172810092267953794611202591069661157992794959838750479208506005687981686025809332691431473809292764988868581099330149458758861391108410825625141738698507086062910615219209815042032904395035912581683751821198857
d: 32680572261276319950892386078453159129961789301515586779730994965995850002546722461272347997633819895532355760655076469284315213156424132333399966484423792583164625536594707257030835906698882316535262007407891728303620471604461013849133230965147690242465484589704113381685121927918786879123393719930911981301
Public key:
N: 72480887416135972061737686062889407161759160887103574047817069443537714713215543172947835307344891172810092267953794611202591069661157992794959838750479208506005687981686025809332691431473809292764988868581099330149458758861391108410825625141738698507086062910615219209815042032904395035912581683751821198857
e: 33917284234023552492304328018336609591997179645740843023623954792230653601864281593260663435095146463818240660159742130550887732511002455913550343095875105353898810744096024635824071115264943251609500722062745618030825015239681817073644641294390347390699708726562812289026328860966096616801710266920990047581
Ciphertext:
c: 15537860445392860627791921113547942268433746816211127779088849816425871267717435366808469771763672942339306019626033112604790279521256018388004503987281369444308463737059894900987688503037651823759352061264031327006538524035092808762774686406194114456168335939404457164139055755834030978327226465998086412320
Plaintext:
m': 34862844108815430278935886114814204661242105806196134451262421197958661737288465541172280522822644267285105893266043422314800759306377373320298160258654603531159702663926160107285223145666239673833817786345065431976764139550904726039902450456522584204556470321705267433321819673919640632299889369457498214445
insecuresolution code
代码语言：javascript复制import random
import math
import secrets
from random import randrange
# 模N大数的幂乘的快速算法
def fastExpMod(b, e, m): # 底数，幂，大数N
result = 1
e = int(e)
while e != 0:
if e % 2 != 0:
e -= 1
result = (result * b) % m
continue
e >>= 1
b = (b * b) % m
return result
def is_probably_prime_miller_rabin(n: int, k: int = 10) -> bool:
# Miller-Rabin 素数判定
# https://gist.github.com/bnlucas/5857478
if n == 2 or n == 3:
return True
if not n & 1:
return False
def check(a: int, s: int, d: int, n: int) -> bool:
x = pow(a, d, n)
if x == 1:
return True
for _ in range(s - 1):
if x == n - 1:
return True
x = pow(x, 2, n)
return x == n - 1
s: int = 0
d: int = n - 1
while d % 2 == 0:
d >>= 1
s = 1
for _ in range(k):
a: int = randrange(2, n - 1)
if not check(a, s, d, n):
return False
return True
def get_big_prime(nbits: int = 512) -> int:
# http://ju.outofmemory.cn/entry/93761
# 返回一个可能是素数的大整数
while True:
p: int = 2 ** (nbits - 1) | secrets.randbits(nbits)
if p % 2 == 0:
p = p 1
if is_probably_prime_miller_rabin(p):
return p
# Generate a textbook RSA key pair
def create_keys(keyLength):
p = get_big_prime(keyLength)
q = get_big_prime(keyLength)
n = p * q
fn = (p - 1) * (q - 1)
e = selectE(fn)
d = match_d(e, fn)
return n, e, d
# 随机在（1，fn）选择一个e， 满足gcd（e,fn）=1
def selectE(fn):
while True:
e = random.randint(0, fn)
if math.gcd(e, fn) == 1:
return e
# 根据e求出其逆元d
def match_d(e, fn):
d = 0
while True:
if (e * d) % fn == 1:
return d
d = 1
# Given a plaintext message and a public key , return the encrypted message.
def encrypt(M, e, n):
return fastExpMod(M, e, n)
# Given a ciphertext message and a private key , return the decrypted message.
def decrypt(C, d, m):
return fastExpMod(C, d, m)
def encrypt_m(in_mess):
c = ''
for ch in in_mess:
s = str(encrypt(ord(ch), e, n))
c = s
return c
def decrypt_m(in_cipher):
p = ''
for ch in in_cipher:
c: str = str(decrypt(ord(ch), d, n))
p = c
return p
if __name__ == '__main__':
# Read a decimal string representing a plaintext message.
mess: str = input("input message:")
# Raise an exception if m is invalid
try:
not mess.isdecimal()
except ValueError:
print('message is invalid')
# Generate a textbook RSA key pair.
n, e, d = create_keys(512)
# Print the private key and the public key as multiple decimal strings.
print("nPrivate key：nN:", n, " nd:", d, )
print("Public key ：nN:", n, " ne:", e, )
# Encrypt the message . Print the encrypted message as a decimal string.
cipher: str = encrypt_m(mess)
print('Ciphertext:nc:', cipher)
# Decrypt the encrypted message . Print the decrypted message as a decimal string.
message: str = decrypt_m(cipher)
print('Plaintext:nm:', message)
print('insecure')受于文本篇幅原因，本文相关算法实现工程例如环境及相关库，无法展示出来，现已将资源上传，可自行点击下方链接下载。
python实现公钥加密RSA算法工程文件
