第四章公钥密码:4.2公钥密码体制的基本概念 422公钥密码算法应满足的要求 ●单向函数 两个集合X、Y之间的一个映射,使得Y中每一元素都有惟一的一个 原像x∈X,且由x易于计算它的像y,由y计算它的原像x是不可行的 易于计算”是指函数值能在其输入长度m的多项式时间内求出,即 求函数值的计算时间复杂度O(m其中a是一固定的常数 ●这时称求函数值的算法属于多项式类P,否则就是不可行的,例如, 函数的输入是n比特,如果求函数值所用的时间是2的某个倍数,则 认为求函数值是不可行的。 易于计算和不可行两个概念与计算复杂性理论中复杂度的概念极为相似, 然而又存在着本质的区别 在复杂性理论中,算法的复杂度是以算法在最坏情况或平均情况时 的复杂度来度量的。这时可能对某些情况很容易求解,复杂度很低 而在此所说的两个概念是指算法在几乎所有情况下的情形 历忠毛孑技*字4.2.2 公钥密码算法应满足的要求  单向函数 ⚫ 两个集合X、Y之间的一个映射，使得Y中每一元素y都有惟一的一个 原像x∈X，且由x易于计算它的像y，由y计算它的原像x是不可行的 ⚫ “易于计算”是指函数值能在其输入长度n的多项式时间内求出，即 求函数值的计算时间复杂度O(n a ),其中a是一固定的常数 ⚫ 这时称求函数值的算法属于多项式类P，否则就是不可行的，例如， 函数的输入是n比特，如果求函数值所用的时间是2 n的某个倍数，则 认为求函数值是不可行的。  易于计算和不可行两个概念与计算复杂性理论中复杂度的概念极为相似， 然而又存在着本质的区别 ⚫ 在复杂性理论中，算法的复杂度是以算法在最坏情况或平均情况时 的复杂度来度量的。这时可能对某些情况很容易求解，复杂度很低 ⚫ 而在此所说的两个概念是指算法在几乎所有情况下的情形 17/ 第四章 公钥密码：4.2 公钥密码体制的基本概念