RSA公钥密码学(数字签名&加密)

浅谈RSA公钥密码学(数字签名技术&加密,包含严格数学证明)  by FORWARD

[数论—现代密码学—非对称密码体制]

①RSA加密算法 ②RSA数字签名算法 ③公共信道上的RSA数字签名算法(加密+签名)

Encrypt()加密运算  PublicKey公钥

Decrypt()解密运算  SecretKey私钥

Sign()签名运算 

明文/消息M  密文C  签名S

(1)RSA加密算法

(i)算法实现

-选择两个互异大素数p,q

-计算:n=pq  φ(n) =(p-1)(q-1)

-随机选择e∈N+,满足gcd(e,φ(n))=1

-找到d∈N+,使得ed≡1(mod φ(n))

记公钥PK={e,n}    私钥SK={d} 

-加密算法(对明文M加密)

C=Enc(M)=M^e(mod n)

-解密算法(对密文C解密还原)

M=Dec(C)=C^d(mod n)

(ii)算法数学证明(解密的唯一性)

证:

C^d(mod n)=(M^e(mod n))^d (mod n)=[(M^e (mod n))(M^e (mod n))*......*(M^e (mod n))] (mod n)=M^ed (mod n)

∵ed≡1 mod(φ(n))

∴ed=kφ(n)+1

By Euler Theorem:M^φ(n)≡1 (mod n)

∴M^(φ(n)+1)≡M (mod n)

∴M^(kφ(n)+1)≡M (mod n)

∴M^(kφ(n)+1)=M (mod n)

∵M<n

∴C^d (mod n)=M

证毕

(2)RSA数字签名算法

(i)算法实现(与加密算法相似)

-选择两个互异大素数p,q

-计算:n=pq  φ(n) =(p-1)(q-1)

-随机选择e∈N+,满足gcd(e,φ(n))=1

-找到d∈N+,使得ed≡1(mod φ(n))

记公钥PK={e,n}    私钥SK={d} 

-签名算法(对消息M签名):

S=Sig(M)=M^d (mod n)

-验证算法(对签名S的验证):

M`=S^e (mod n)

若M`=M,则签名S属实/不可抵赖

(ii)算法数学证明(验证的唯一性)

证:

M`=S^e (mod n)=(M^d (mod n))^e (mod n)=[(M^d (mod n))(M^d (mod n)*.....*(M^d (mod n))] (mod n)=M^de (mod n)

∵de≡1 mod(φ(n))

∴de=kφ(n)+1

By Euler Theorem:M^φ(n)≡1 (mod n)

∴M^(φ(n)+1)≡M (mod n)

∴M^(kφ(n)+1)≡M (mod n)

∴M^(kφ(n)+1)=M (mod n)

∵M<n

∴M`=S^e (mod n)=M

证毕

③在公共信道下的数字签名算法实现(签名+加密)

记发送者A, 接收者B ,消息M,密文C

记A的公钥PK1,私钥SK1

记B的公钥PK2,私钥SK2

算法实现:

-选择两个互异大素数p1,q1

-计算:n1=p1q1  φ(n) =(p1-1)(q1-1)

-随机选择e1∈N+,满足gcd(e1,φ(n1))=1

-找到d1∈N+,使得e1d1≡1(mod φ(n1))

记A的公钥PK1={e1,n1},私钥SK1={d1} 

-选择两个互异大素数p2,q2

-计算:n2=p2q2  φ(n2) =(p2-1)(q2-1)

-随机选择e2∈N+,满足gcd(e2,φ(n2))=1

-找到d2∈N+,使得e2d2≡1(mod φ(n2))

记B的公钥PK2={e2,n2},私钥SK2={d2} 

签名算法(对M签名):

S=Sig(M)=M^d1 (mod n1)

包装算法(对S包装):

C=Enc(S)=S^e2 (mod n2)

拆包算法(对C拆包):

S=Dec(C)=C^d2 (mod n2)

验证算法(对S验证)

M`=S^e1 (mod n1)

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 213,014评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,796评论 3 386
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 158,484评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,830评论 1 285
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,946评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,114评论 1 292
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,182评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,927评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,369评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,678评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,832评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,533评论 4 335
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,166评论 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,885评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,128评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,659评论 2 362
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,738评论 2 351

推荐阅读更多精彩内容

  • 所有货币都需要一些方法来控制供应,并强制执行各种安全属性以防止作弊。在法定货币方面,像中央银行这样的组织控制货币供...
    Nutbox_Lab阅读 3,083评论 1 3
  • 转:https://blog.csdn.net/m0_37458552/article/details/80250...
    right_33cb阅读 10,214评论 0 0
  • RSA RSA算法是目前应用最广泛的公钥密码体制之一。RSA算法的安全性是给予大整数因子分解的困难性。RSA名字是...
    Carrism阅读 8,419评论 1 0
  • 数字签名    ——消息到底是谁写的 数字签名的应用实例 安全信息公告  一些信息安全方面的组织会在其网站上发布一...
    Invincibled阅读 1,459评论 0 2
  • 16宿命:用概率思维提高你的胜算 以前的我是风险厌恶者,不喜欢去冒险,但是人生放弃了冒险,也就放弃了无数的可能。 ...
    yichen大刀阅读 6,042评论 0 4