西安电子科技大学：《现代密码学》课程教学资源（PPT课件讲稿）第五章 公钥密码（数论简介、公钥密码体制的基本概念 Basic Concept of Public Key Cryptography、RSA算法）

公钥密码 ■数论简介 ■公钥密码体制的基本概念 ■RSA算法 ■椭圆曲线密码体制 2021/2/21

2021/2/21 2 公钥密码 ◼ 数论简介 ◼ 公钥密码体制的基本概念 ◼ RSA算法 ◼ 椭圆曲线密码体制

教论简介 2021/2/21

2021/2/21 3 数论简介

寓散对数 ■定理:设日的阶为m,则ak≡1modn的充分必 要条件是k是m的倍教 推论:a的阶整除φ(n)。 ■本原根:a的阶m等于φ(),a为n的本原根。 ■如票a是n的本原根,a1,a2,a在模n下互不 相同且与η互素。 ■本原根不唯一。 ■并非所有元素都有本原根,仅有以下形式的整 数才有本原根:2,4,p,2p,p是奇素数 2021/2/21

2021/2/21 4 离散对数 ◼ 定理：设a的阶为m，则a k≡1mod n的充分必 要条件是k是m的倍数。 ◼ 推论：a的阶整除j(n)。 ◼ 本原根：a的阶m等于j(n)，a为n的本原根。 ◼ 如果a是n的本原根，a 1 ,a2 ,...,a j(n)在模n下互不 相同且与n互素。 ◼ 本原根不唯一。 ◼ 并非所有元素都有本原根，仅有以下形式的整 数才有本原根：2，4，p a ,2pa , p是奇素数

寓散对数 指标 y=ax(a>O,a≠1)的逆函数称为以a为底的对 数,记为x=logy 设p为素数,a是p的本原根,则a°,a ·●·9 a p-1 产生1到p-1中所有值,且每个值只出现一次。 对任一b∈{1,pP-1},都存在唯一的i(1≤i ≤p),使b≡ a'mod po i称为模p下以a为底b 的指标,记为i=inda,p(d p 2021/2/21 5

2021/2/21 5 离散对数 ◼ 指标 ◼ y=ax (a>0,a≠1)的逆函数称为以a为底的对 数，记为x=logay ◼ 设p为素数，a是p的本原根，则a 0 ,a1 ,...,a p-1 产生1到p-1中所有值，且每个值只出现一次。 对任一b∈{1,…,p-1}，都存在唯一的i(1≤i ≤p)，使b≡ai mod p。i称为模p下以a为底b 的指标，记为i=inda,p(d)

寓散对数 指标的性质 inda, p (1)=0 2. indap(a=1 3. inda, p(xy)=[inda, p (x)+ inda, p( y)] mod op(p) 4. inda, p y =[rxinda D(y] mod o(p) 后两个性质基于下列结论 若a≡amdp,a和p互素,则z≡ q mod p(p) 2021/2/21 6

2021/2/21 6 离散对数 ◼ 指标的性质 1. inda,p(1)=0 2. inda,p(a)=1 3. inda,p(xy)=[inda,p(x)+ inda,p(y)] mod j(p) 4. inda,p(yr)=[r×inda,p(y)] mod j(p) 后两个性质基于下列结论 若a z≡aq mod p ,a和p互素，则z ≡q mod j (p)

离散对教 ■设p是素数,a是p的本原根。对 b∈{1,P-1},有唯一的∈{1,,p-1}使 b≡ a'mod p。称为模P下以a为底b的高 散对数,记为 i≡ loga b(modp) ■巳知a,p,,求b比较容易,以及a,b,p,求i非井 幸因难 2021/2/21

2021/2/21 7 离散对数 ◼ 设p是素数，a是p的本原根。对 b∈{1,…,p-1},有唯一的i ∈{1,…,p-1},使 b≡ai mod p。称i为模p下以a为底b的离 散对数，记为 i ≡logab (mod p) ◼ 已知a,p,i,求b比较容易，以及a,b,p,求i非 常困难

公钥密码体制的基本概念 Basic Concept of Public Key Cryptography 2021/2/21

2021/2/21 8 公钥密码体制的基本概念 Basic Concept of Public Key Cryptography

公钥密码体制的原狸 公钥体制( Public key system)Oife和 Hellman,1976) 每个用户都有一对选定的密钥(公钥k;私钥k2),公开的 密钥k可以像电话号码一样进行注册公布。 主要特点 ■如密和解密能力分开 多个用户加密的峭息只能由一个用户解读,(用于公共 网络中实现保密通信 ■只能由一个用户加密消息而使多个用户可以解读(可用 于认证糸统中对消息进行数字签字 无需事先分配密钥。 2021/2/21

2021/2/21 9 公钥密码体制的原理 公钥体制(Public key system)(Diffie和Hellman,1976) 每个用户都有一对选定的密钥(公钥k1；私钥k2 )，公开的 密钥k1可以像电话号码一样进行注册公布。 主要特点： ◼ 加密和解密能力分开 ◼ 多个用户加密的消息只能由一个用户解读，（用于公共 网络中实现保密通信） ◼ 只能由一个用户加密消息而使多个用户可以解读（可用 于认证系统中对消息进行数字签字）。 ◼ 无需事先分配密钥

忪钥体制加密 密码分析员 SK 发送者A 加密算法 解密算法 接收者B PKB SKB 密钥源 公钥体制加、解密m=D(d=DKB(EpkB(m) 安金保障 从公开钥PB和密文c要推出明文m或解密钥SKB在计算上是 不可行的。 由于任一用户都可用用户B的公开钥PKB向他发送机密消息, 因而密文C不具有认证性。 2021/2/21

2021/2/21 10 公钥体制加密 公钥体制加、解密 m=D (c)=DSKB (EPKB(m)) 安全保障 •从公开钥PKB和密文c要推出明文m或解密钥SKB在计算上是 不可行的。 •由于任一用户都可用用户B的公开钥PKB 向他发送机密消息， 因而密文c不具有认证性。 发送者A 加密算法 PKB 密钥源 SKB 解密算法 接收者B 密码分析员 m c m m’ SK’B

松钥密码认证体制 用户A以自已的秘密钥Sk对峭息m迸行A的专用变换 DKA,A计算密文:C=Dg(m送给用户B,B验证C: =EpKa (c)=EpKA( DSKA(m) 安全性: 由于Sk是保密的,其他人都不可能伪造密文c,可用A 的公开钥解密附得到有意义的诮息m。因此可以验证消息 m来自A而不是其他人,而实现了对A所发消息的认证。 2021/2/21

2021/2/21 11 公钥密码认证体制 用户A以自己的秘密钥SkA对消息m进行A的专用变换 DSKA，A计算密文：c=DSKA(m)送给用户B，B验证c： m=EPKA（c）=EPKA(DSKA(m)) 安全性： 由于SkA是保密的，其他人都不可能伪造密文c，可用A 的 公开钥解密时得到有意义的消息m。因此可以验证消息 m来自A而不是其他人，而实现了对A所发消息的认证