文档介绍：公钥密码的理论基础
RSA 公钥密码
RSA公钥密码体制
RSA的安全性讨论
模n求逆的方法
模n的大数幂乘的快速算法
因子分解
大素数生成
第五章公钥密码
1976年,。在公钥密码体制中,加密密钥(Public-key)和解密密钥(private-key)是不一样的,由两者任何一个不能推出另一个,本章介绍RSA公钥密码体制,ElGamal公钥密码体制,Menezes-Vanstone公钥密码体制以及一些相关知识。
公钥密码的理论基础是单向函数。
公钥密码的理论基础
设f 是一个函数。如果对任意给定的x,计算y使得y=f(x)是容易的,但对任意给定的y ,计算x 使 y=f(x) 是难解的,即求 f 的逆函数是难解的,则称y=f(x)是一个单向函数(one-way function)。
设f 是一个函数,t 是与f有关的一个参数,对任意给定的x,计算y 使得 y=f(x)是容易的,如果当不知参数t 时,计算 f 的逆函数是难解的,但当知道参数t 时,计算f 的逆函数是容易的,则称f 是一个陷门单向函数(trapdoor one-way function),参数t 称为陷门。
在公钥密码中,加密变换是一个陷门单向函数。
RSA 公钥密码
基本的数论知识
设 a,b,n都是整数。如果n|(a-b) 则称 a 和 b 模 n同余,记为, n 称为这个同余式的模。
同余的性质:
(中国剩余定理)设是两两互素的正整数,设是整数。则同余方程组
模有唯一解:
证明: 对任意,考虑
下面我们来证明式()是同余方程组()的模唯一解,假设和是同余方程组()的两个解,即
因此,式()是同余方程组()的模唯一解。
则
即
故
例1 (孙子算经中物不知数)今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?
解:
例2 (韩信点兵)有兵一对,若列5行纵队,则末行1人,成6行纵队,则末行5人,成7行纵队,则末行4人,成11行纵队,?
解:
Euler函数
定义设n是一个正整数。
称为Euler函数。Euler函数是定义在正整数集合上的函数。
由定义可以立即得出,如果p是一个素数,则
如果
证明:
如果
证明: 首先证明对于任意素数和任意正整数有
,我们有