Program : Textbook RSA (on group)
In this part, you are required to implement the textbook RSA algorithm for signing from scratch. The signing procedure is quite similar with encryption, but you should not be confused with them. 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
Example Input & Output
Input:
代码语言：javascript复制34862844108815430278935886114814204661242105806196134451262421197958661737288465541172280522822644267285105893266043422314800759306377373320298160258654603531159702663926160107285223145666239673833817786345065431976764139550904726039902450456522584204556470321705267433321819673919640632299889369457498214445Output:
代码语言：javascript复制Private key:
N: 60578014255102269896133371904627262317416253087521326961353447386111108220456127698087451094233400895389904195033258942460533045725424252051031082346623918833115880605331217845541371778050413570487118811797680786863916249631173243202415281126677535724142072672389239932425514746354116788337452709735978693441
d: 29794267204372868920195293823377577521348286669753768926422253485197790892996900859124258444603569195973796199037022534122349660497314477050901363975617785986341374781520104383687018770714375371190852092718547427166813248293087229107819441125188332290624176181241072609675470769160255268721140521999754996495
Public key:
N: 60578014255102269896133371904627262317416253087521326961353447386111108220456127698087451094233400895389904195033258942460533045725424252051031082346623918833115880605331217845541371778050413570487118811797680786863916249631173243202415281126677535724142072672389239932425514746354116788337452709735978693441
e: 50236051684532724158959956908047535011547027752807918443381101532977239879805272363541815186678432878182913685573432227040470122555922161989827750747871310928207045877463632837569381571438481188390948780929921154288163100313907723263741344747325268803766335694293737307011671572842257344517928948772977494407
Signature:
s: 34580775293086014798734721087900779255336448150833662767477345836086991760074172833491041507919156367652845778336488884879942244053190133044473935740553882083350076369679814132582396981838752038660178872674779525999874634128284351865411689078895902069902392417208340043916976695929474980926586642060201969134
Verify s of m:
valid
m' (faked): 50450048059881262533055051783615244680711671489653790401184574597060270328158473249590629579575748444416670136818805407617798193709438157542915258506987898524296742253334657876701634724978818355153836962043088167025161694157068501323069379606742460252729290661161539614496733300584141680283224222741900536312
Verify s of m':
invalid
s' (faked): 28243222593155363957786267188064169499833133908722962853038127116797113724411953085666999176421008597106689088871876968450636497620934133534312574374692406966037865626499421933604018821681836276566498093397822394074799560633387005572367768063152314140663154660143389779133176949492679329809464448869998812303
Verify s' of m:
invalidsolution code
代码语言：javascript复制# Program 1: Textbook RSA (on group)
from random import randrange
import secrets
import random
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) -> int:
# http://ju.outofmemory.cn/entry/93761
# 返回一个可能是素数的大整数
while True:
p: int = 2 ** (nbits - 1) | secrets.randbits(nbits)
# Miller_Robin算法对2的倍数检测有异常，故如果生成2的倍数，则将其 1再进行判断:
if p % 2 == 0:
p = p 1
if is_probably_prime_miller_rabin(p):
return p
def E_create(min_num: int, max_num: int) -> int:
while 1:
prime_ran: int = random.randint(min_num, max_num)
if prime_ran % 2 == 0:
prime_ran = 1
if is_probably_prime_miller_rabin(prime_ran):
break
return prime_ran
# 定义扩展欧几里得算法:
def ex_gcd(a, b) -> tuple:
if b == 0:
return 1, 0, a
else:
x, y, q = ex_gcd(b, a % b)
x, y = y, (x - (a // b) * y)
return x, y, q
# 生成p,q:
p: int = get_big_prime(512)
q: int = get_big_prime(512)
n: int = p * q
# 求n:
phi_n: int = (p - 1) * (q - 1)
print('Private key:n', 'N:n', n)
# 选择与n互素的e:
e: int = E_create(pow(2, 1023), n)
# 输出d(逆元):
d: int = ex_gcd(e, phi_n)[0]
print('d:n', d)
print('Public key:n', 'N:n', n)
print('e:n', e)
# Read a decimal string representing a plaintext message m.
# Raise an exception if m is invalid:
plaintext: str = input('input the plaintext:n')
if int(plaintext) < 0:
raise ValueError
# Sign the message m. Print the signature as a decimal string.:
s: int = pow(int(plaintext), d, n)
print('nSignature:ns:n', s)
plaintext_ver: int = pow(s, e, n)
print("Verify s of m:")
# Verify the signature of message .
if plaintext_ver == int(plaintext):
print("valid")
else:
print("invalid")
# Randomly pick a number as a faked message
plaintext_rnd: int = random.randint(pow(2, 1023), pow(2, 1024))
# verify the signature of message .
s_1: int = pow(plaintext_rnd, d, n)
plaintext_ver_1: int = pow(s_1, e, n)
print("m' (faked):n", plaintext_ver_1)
print("Verify s of m':")
if plaintext_ver_1 == int(plaintext):
print("valid")
else:
print("invalid")
# Randomly pick a number as a faked signature
s_2: int = random.randint(pow(2, 1023), pow(2, 1024))
# verify the signature of message .
plaintext_ver_2: int = pow(s_2, e, n)
print("s' (faked):n", s_2)
print("Verify s' of m:")
if plaintext_ver_2 == int(plaintext):
print("valid")
else:
print("invalid")output
代码语言：javascript复制Private key:
N:
107992477274908164987809018982137465564341257948530534670895468253588173010564882417126177146346874580504385069923226798367938945288000617850204675720872151991186552635061582413680375021707167755890634233530984429873649065257813075105561239616924445227718402281860904991925881636947897086171490852246792807907
d:
17744715076567138746128060295691002556825632322161828767604820119356827152927789620314560931112894682961782585787136528959807210900338073162455547178040283671382890616336830904427664840597925533292107378532037380901265512367128033731853434723924570798499611024587619694890298771860154109313171748776601333531
Public key:
N:
107992477274908164987809018982137465564341257948530534670895468253588173010564882417126177146346874580504385069923226798367938945288000617850204675720872151991186552635061582413680375021707167755890634233530984429873649065257813075105561239616924445227718402281860904991925881636947897086171490852246792807907
e:
100803639898282871899084573118859880269834136605111141139254190439351190893900619928757241680252089032822142221998467989929656318316845297145036079246329112459152582829874283395938059580016215735704690622809229105159553683337736444067606804910236012658551365119515445807535745830975271663875154185122545033491
input the plaintext:
34862844108815430278935886114814204661242105806196134451262421197958661737288465
54117228052282264426728510589326604342231480075930637737332029816025865460353115
97026639261601072852231456662396738338177863450654319767641395509047260399024504
56522584204556470321705267433321819673919640632299889369457498214445
Signature:
s:
1513270751288809861781429681060507518418033500789107714991292485468275765887699169898521568123488506773451069632714191529063001321406797834199470047305211644533172136649804510006662987613553008630342936317048697038496511225968282373331989596122475926265089012209697077873774877118997027968381890785849649178
Verify s of m:
valid
m' (faked):
100752093311910077742499757370470112147480890616144299651911253300500673042559683581450698353287657998135695042769358738816482816638086436658380699433222424662154214377632914864992524159313615028280496814879902273096128183574373734203981481552510513025517392392561681223897987300529620089982250914081084216265
Verify s of m':
invalid
s' (faked):
168822314496642584742692020936702019211695198104472330305707135494052699548229026068527368035464885976889603265835100106190989646443223382742932777599773760255418327460947037914104380927379145270494735030046695346724036443686835579839749199126417321843932478200276140840192924841477228546822936072321697722472
Verify s' of m:
invalid
进程已结束，退出代码为 0A screenshot of the console output of the program：
受于文本篇幅原因，本文相关算法实现工程例如环境及相关库，无法展示出来，现已将资源上传，可自行点击下方链接下载。
python实现签名RSA算法工程文件
