算法分析
- RSA簽名方案是目前使用較多的一個(gè)簽名方案巩踏，它的安全性是基于大整數(shù)因式分解的困難性限府。
- 主要包括算法：
-
秘鑰生成算法：
-
簽名算法：
驗(yàn)證算法：
算法實(shí)現(xiàn)
# 直接導(dǎo)入之前寫好的RSA算法和hash函數(shù)的hashlib庫(kù)
from RSA import *
import hashlib
# 秘鑰生成算法
pubkey = []
selfkey = []
'''公鑰私鑰中用到的兩個(gè)大素?cái)?shù)數(shù)p,q衣摩，都是1024位'''
p = 106697219132480173106064317148705638676529121742557567770857687729397446898790451577487723991083173010242416863238099716044775658681981821407922722052778958942891831033512463262741053961681512908218003840408526915629689432111480588966800949428079015682624591636010678691927285321708935076221951173426894836169
q = 144819424465842307806353672547344125290716753535239658417883828941232509622838692761917211806963011168822281666033695157426515864265527046213326145174398018859056439431422867957079149967592078894410082695714160599647180947207504108618794637872261572262805565517756922288320779308895819726074229154002310375209
'''生成公鑰私鑰'''
pubkey, selfkey = gen_key(p, q)
# 簽名算法
m = b"helloworld"
md = hashlib.md5()
md.update(m)
# 用MD5算法生成消息摘要hm
hm = int(md.hexdigest(), 16)
print("Alice生成的消息摘要為： \n", hm)
# 計(jì)算簽名
# Alice用自己的私鑰計(jì)算簽名s
s = encrypt(hm, selfkey)
print("Alice計(jì)算出的簽名s為: \n", s)
# Alice將(m, s)發(fā)送個(gè)Bob
# 驗(yàn)證算法
# Bob驗(yàn)證簽名是否有效
flag = True
# Bob用公鑰計(jì)算出消息摘要
res = decrypt(s, pubkey)
print("Bob計(jì)算出的消息摘要為： \n", res)
if res == hm:
flag =True
else:
flag = False
# 將驗(yàn)證結(jié)果輸出
if flag == True:
print("Alice的簽名有效")
else:
print("Alice的簽名無(wú)效")
簽名與驗(yàn)證過(guò)程
如下圖所示呢蔫，消息m = “helloworld” , 使用RSA算法中生成的公鑰和私鑰攀唯，Alice通過(guò)私鑰對(duì)消息摘要進(jìn)行簽名得到s , Bob通過(guò)公鑰根據(jù)簽名s計(jì)算出消息摘要，并將其與Alice發(fā)來(lái)的消息摘要進(jìn)行對(duì)比友浸，如果相等拆又，則打印出簽名有效，否則打印出簽名無(wú)效温兼。
正確性
簽名驗(yàn)證過(guò)程的正確性證明如下：
安全性分析
簽名中使用了hash函數(shù)秸滴，哈希函數(shù)的使用使簽名具有更好的抗攻擊性。如果不使用募判，則可根據(jù)RSA方案所具有的同態(tài)特性荡含，根據(jù)已知的兩個(gè)簽名，生成偽造的消息簽名届垫。具體如下：如果消息??1释液、??2的簽名分別是??1和??2，則任何知道??1装处，??1均澳，??2，??2的人可以偽造對(duì)消息??1??2的簽名??1??2符衔，因?yàn)?br> ??????(??1??2) = ??????(??1)??????(??2)
-
若未使用hash函數(shù)找前，還可以嘗試一般攻擊：攻擊者任選一個(gè)數(shù)據(jù)??，用A的公鑰計(jì)算??＝Y(jié)^e?????? ?? 于是便可以用Y偽造A對(duì)消息X的簽名判族，因?yàn)?/p>
存在簽名的可重用性問(wèn)題躺盛，即對(duì)同一消息在不同時(shí)刻簽名是相同的。這個(gè)問(wèn)題可通過(guò)在每次簽名中引入不同隨機(jī)數(shù)來(lái)解決形帮。
