admin管理员组

文章数量:815283

python实现签名RSA算法

⭐本专栏主要用python实现密码学中的常用经典算法,例如Vigenere、3DES、RSA、ElGamal、Diffie-Hellman、RSA签名、ElGamal签名、HMAC、哈希算法、列移位、AES等等。
🔥文章和代码已归档至【Github仓库:cryptography-codebase】,需要的朋友们自取。或者公众号【AIShareLab】回复 密码学 也可获取。

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.

  • KeyGen
    • Same as before.
  • Sign
    • Given a plaintext message m ∈ Z N m \in \mathbb{Z}_N m∈ZN​ and a private key ( N , d ) (N,d) (N,d), return the signature s s s.
  • Verify
    • Given a plaintext message m ∈ Z N m \in \mathbb{Z}_N m∈ZN​, the signature s s s, and a public key ( N , e ) (N,e) (N,e), check whether the signature is valid or not.

Your program does the following:

  • Generate a textbook RSA key pair. Print the private key and the public key as multiple decimal strings.
  • Read a decimal string representing a plaintext message m m m. Raise an exception if m m m is invalid.
  • Sign the message m m m. Print the signature s s s as a decimal string.
  • Verify the signature s s s of message m m m. Print valid if the signature is valid. Print invalid otherwise.
  • Randomly pick a number as a faked message m ′ m^\prime m′, and verify the signature s s s of message m ′ m^\prime m′. Print valid if the signature is valid. Print invalid otherwise.
  • Randomly pick a number as a faked signature s ′ s^\prime s′, and verify the signature s ′ s^\prime s′ of message m m m. Print valid if the signature is valid. Print invalid otherwise.

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:

34862844108815430278935886114814204661242105806196134451262421197958661737288465541172280522822644267285105893266043422314800759306377373320298160258654603531159702663926160107285223145666239673833817786345065431976764139550904726039902450456522584204556470321705267433321819673919640632299889369457498214445

Output:

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:
invalid

solution code

# Program 1: Textbook RSA (on group)
from random import randrange
import secrets
import randomdef is_probably_prime_miller_rabin(n: int, k: int = 10) -> bool:# Miller-Rabin 素数判定#  n == 2 or n == 3:return Trueif not n & 1:return Falsedef check(a: int, s: int, d: int, n: int) -> bool:x = pow(a, d, n)if x == 1:return Truefor _ in range(s - 1):if x == n - 1:return Truex = pow(x, 2, n)return x == n - 1s: int = 0d: int = n - 1while d % 2 == 0:d >>= 1s += 1for _ in range(k):a: int = randrange(2, n - 1)if not check(a, s, d, n):return Falsereturn Truedef get_big_prime(nbits: int) -> int:#  返回一个可能是素数的大整数while True:p: int = 2 ** (nbits - 1) | secrets.randbits(nbits)# Miller_Robin算法对2的倍数检测有异常,故如果生成2的倍数,则将其+1再进行判断:if p % 2 == 0:p = p + 1if is_probably_prime_miller_rabin(p):return pdef 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 += 1if is_probably_prime_miller_rabin(prime_ran):breakreturn prime_ran# 定义扩展欧几里得算法:
def ex_gcd(a, b) -> tuple:if b == 0:return 1, 0, aelse: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

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进程已结束,退出代码为 0

A screenshot of the console output of the program:

本文标签: python实现签名RSA算法