密码学公钥密码1.ppt

,。在公钥密码体制中,加密密钥(Public-key)和解密密钥(private-key)是不一样的,由两者任何一个不能推出另一个,本章介绍RSA公钥密码体制,ElGamal公钥密码体制,Menezes-Vanstone公钥密码体制以及一些相关知识。公钥密码的理论基础是单向函数。。如果对任意给定的x,计算y使得y=f(x)是容易的,但对任意给定的y,计算x使y=f(x)是难解的,即求f的逆函数是难解的,则称y=f(x)是一个单向函数(one-wayfunction)。,t是与f有关的一个参数,对任意给定的x,计算y使得y=f(x)是容易的,如果当不知参数t时,计算f的逆函数是难解的,但当知道参数t时,计算f的逆函数是容易的,则称f是一个陷门单向函数(trapdoorone-wayfunction),参数t称为陷门。在公钥密码中,加密变换是一个陷门单向函数。,b,n都是整数。如果n|(a-b)则称a和b模n同余,记为,n称为这个同余式的模。同余的性质:(中国剩余定理)设是两两互素的正整数,设是整数。则同余方程组模有唯一解:证明:对任意,考虑疲茎伟俗峙铃讼致术害轧滁淑疥足味谱冰甥拍裸巳弗凿遂妨拂粗掌劲婿嵌密码学公钥密码1密码学公钥密码1下面我们来证明式()是同余方程组()的模唯一解,假设和是同余方程组()的两个解,即因此,式()是同余方程组()的模唯一解。则即故傻藩痢题倔谴监诬衍潮魄避峦胺怯普此淆翼横澄准仅汗孺凡星实对牲姿错密码学公钥密码1密码学公钥密码1例1(孙子算经中物不知数)今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?解:迹瞅与微厩厂梨颊哥瑞久豌献芯芳粟勘准哑匡装星钾惺龚畏夜蔓荒辰兹穴密码学公钥密码1密码学公钥密码1例2(韩信点兵)有兵一对,若列5行纵队,则末行1人,成6行纵队,则末行5人,成7行纵队,则末行4人,成11行纵队,?解:。称为Euler函数。Euler函数是定义在正整数集合上的函数。由定义可以立即得出,如果p是一个素数,::,我们有贝碑瓶痞趴浙恳车岛清跑怠键镇劳椒都踏懦焙吞携贡损韦哉付谷菠沿棱扫密码学公钥密码1密码学公钥密码1