9.1.1离散对数问题回顾 如果a是素数p的一个原根(本原元素),则 a mod p,a2modp,……,ap- mod p,生成模p的完全剩余集 {1,2 ·"■··· 对于所有素数,其原根必定存在,即 对于一个整数b和素数p的一个原根,可以找到唯一的指数,使得 b= a' mod p,其中0<=i<=p-1 指数i为b的以a为基数的模p的离散对数或者指数。 〉离散对数密码体制的安全性基于DLP问题,在下式中已知C和P 的情况下,由d求M很容易,由M求d很困难, d= log M in GF(P), 最快的算法需要T=eXp(n(Pnn(P)/2)次运算。当P是200 位时,T=2.7×101,如果1us解一次,需要2~3天;如果P 664位,则T=12×1023,约1012天或2.739X109年,约2.7亿 年只要P是够大可以达到足够安年 mfy@ustc.edu.cn 现代密码学理论与实践 7/54mfy@ustc.edu.cn 现代密码学理论与实践 7/54  如果a是素数p的一个原根(本原元素)，则 a mod p, a2 mod p, ......, ap-1 mod p，生成模p的完全剩余集 {1, 2, ......, p-1} 对于所有素数，其原根必定存在，即 对于一个整数b和素数p的一个原根，可以找到唯一的指数i, 使得 b = a i mod p, 其中 0<= i <= p-1 指数i称为b的以a为基数的模p的离散对数或者指数。  离散对数密码体制的安全性基于DLP问题, 在下式中已知C和P 的情况下, 由d求M很容易, 由M求d很困难, d = logCM in GF(P),  最快的算法需要T=exp((ln(P)lnln(P)1/2)次运算。当P是200 位时, T = 2.7x1011 , 如果1μs解一次, 需要2~3天；如果P = 664位, 则T = 1.2x1023 , 约1012天或2.739x109年, 约2.7亿 年. 只要P足够大,可以达到足够安全