公钥密码 ■数论简介 ■公钥密码体制的基本概念 ■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)