第四章公钥密码: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 公钥密码体制的基本概念
第四章公钥密码:4.2公钥密码体制的基本概念 422公钥密码算法应满足的要求 ●陷门单向函数 称一个函数是陷门单向函数,是指该函数是易于计算的, 但求它的逆是不可行的,除非再已知某些附加信息。当 附加信息给定后,求逆可在多项式时间完成 总结为:陷门单向函数是一族可逆函数k,满足 ①当k和X已知时,YA(X易于计算 ②当和知时,X(Y易于计算 ③当知但未知时,X4(计算上是不可行的 ≥研究公钥密码算法就是要找出合适的陷门单向函数 历忠毛孑技*字 18
4.2.2 公钥密码算法应满足的要求 陷门单向函数 ⚫ 称一个函数是陷门单向函数，是指该函数是易于计算的， 但求它的逆是不可行的，除非再已知某些附加信息。当 附加信息给定后，求逆可在多项式时间完成 总结为： 陷门单向函数是一族可逆函数fk，满足 ⚫ ①当k和X已知时，Y=fk (X)易于计算 ⚫ ②当k和Y已知时，X=fk -1 (Y)易于计算 ⚫ ③当Y已知但k未知时，X=fk -1 (Y)计算上是不可行的 研究公钥密码算法就是要找出合适的陷门单向函数 18/ 第四章 公钥密码：4.2 公钥密码体制的基本概念
第四章公钥密码:4.2公钥密码体制的基本概念 422公钥密码算法应满足的要求 ●用于构造单向陷门函数的典型困难问题及算法 ●RSA(基于大数分解困难问题 RSA系列算法, Rabin体制 DLP(基于求解有限域上离散对数困难问题) EGama加密体制,DH密钥交换 Ecc(椭圆曲线离散对数问题) ●ECC上双线性对,EcC上基于身份的密码体制 基于格的概率加密体制(基于求解格上最短向量等问题) ●NTRU 基于纠错码的体制McE|ice 背包体制 历忠毛孑技*字 19
4.2.2 公钥密码算法应满足的要求 用于构造单向陷门函数的典型困难问题及算法 ⚫ RSA(基于大数分解困难问题) ⚫ RSA系列算法，Rabin体制 ⚫ DLP (基于求解有限域上离散对数困难问题) ⚫ ElGamal加密体制，DH密钥交换 ⚫ ECC(椭圆曲线离散对数问题) ⚫ ECC上双线性对，ECC上基于身份的密码体制 ⚫ 基于格的概率加密体制(基于求解格上最短向量等问题) ⚫ NTRU… ⚫ 基于纠错码的体制McElice… ⚫ 背包体制 19/ 第四章 公钥密码：4.2 公钥密码体制的基本概念
第四章公钥密码:4.2公钥密码体制的基本概念 422公钥密码算法应满足的要求 ●量子公钥密码 基于量子编码、量子不可克隆定理、子集和问题等困难性的公钥密 码算法,但是目前这些问题的困难性也受到质疑 后量子密码学post- quantum cryptograph ●量子计算具有内在并行性,能攻破RSA、离散对数、ECc等体制 06年在比利时鲁汶天主教大学召开了第一次后量子密码学国际会议 Daniel J, Bernstein Johannes Buchmann Erik Dahmen , post- Quantum Cryptography, Springer-Verlag, pp 245, 2009 ●几种量子计算尚不能征服的密码体制 基于Hash的密码(Hash- based cryptography) 如 Merkle于1979年提出的hash树公钥签名体制,按 Lamport和Dfil的 单消息签名概念构建的 历忠毛孑技*字 20/
4.2.2 公钥密码算法应满足的要求 量子公钥密码 ⚫ 基于量子编码、量子不可克隆定理、子集和问题等困难性的公钥密 码算法，但是目前这些问题的困难性也受到质疑 后量子密码学post-quantum cryptography ⚫ 量子计算具有内在并行性，能攻破RSA、离散对数、ECC等体制 ⚫ 06年在比利时鲁汶天主教大学召开了第一次后量子密码学国际会议 ⚫ Daniel J. Bernstein, Johannes Buchmann, Erik Dahmen, “PostQuantum Cryptography,” Springer-Verlag, pp.245, 2009. 几种量子计算尚不能征服的密码体制 ⚫ 基于Hash的密码（Hash-based cryptography） ⚫ 如Merkle于1979年提出的hash树公钥签名体制，按Lamport和Diffie的 单消息签名概念构建的 20/ 第四章 公钥密码：4.2 公钥密码体制的基本概念
第四章公钥密码:4.2公钥密码体制的基本概念 422公钥密码算法应满足的要求 基于编码(纠错码)的密码(code- based cryptography) 如 McEliece1978年提出的隐 Goppa码公钥加密体制。 王新梅教授提出的新梅算法 ●基于格的密码( Lattice-based cryptography) Hoffstein- Pipher-Silverman于1998年提出的“NTRU”公钥加 密体制,虽不是第一个,但为最引人注目的一个 多变量二次方程密码( Multivariate- quadratic-equations cryptography) 如 Patarin于1996年提出的“HFEv”公钥签名体制就是几个重要 例子中的一个,此例后为 Matsumoto和ma所推广 秘密(单)钥密码( Secret-key cryptography) ●如高级数据加密标准AES 历忠毛孑技*字
4.2.2 公钥密码算法应满足的要求 ⚫ 基于编码（纠错码）的密码（Code-based cryptography） ⚫ 如McEliece1978年提出的隐Goppa码公钥加密体制。 ⚫ 王新梅教授提出的新梅算法 ⚫ 基于格的密码（Lattice-based cryptography） ⚫ Hoffstein-Pipher-Silverman于1998年提出的“NTRU”公钥加 密体制，虽不是第一个，但为最引人注目的一个 ⚫ 多变量二次方程密码（Multivariate-quadratic-equations cryptography) ⚫ 如Patarin于1996年提出的“HFEv-”公钥签名体制就是几个重要 例子中的一个，此例后为Matsumoto和Imai所推广 ⚫ 秘密（单）钥密码（Secret-key cryptography） ⚫ 如高级数据加密标准AES 21/ 第四章 公钥密码：4.2 公钥密码体制的基本概念