公钥密码学与软件实现要点.pdf

2011 ©谷安天下版权所有 公钥密码学与软件实现要点公钥密码学与软件实现要点 沈海峰 2011 ©谷安天下版权所有 目录  公钥密码学简介 公钥密码学基本原理 公钥密码学的应用 软件实现公钥算法的要点 2011 ©谷安天下版权所有 公钥密码学简介 2011 ©谷安天下版权所有 公钥密码学简介 密码学分两大类：  对称密码学  非对称（公钥）密码学 对称密码学的两大缺陷：  密钥分配困难： 密钥量大 没有高效的分配途径  不能用于数字签名 单纯加密不能确认消息的真实性（中间人攻击） 2011 ©谷安天下版权所有 公钥密码学简介 单纯加密的中间人攻击 2011 ©谷安天下版权所有 公钥密码学简介 1976年，斯坦福大学的Diffie、Hellman针对以上问题，合作发表论 文《密码学的新方向》，宣告公钥密码学的诞生：  颠覆了几千年的密码学传统  解决了密钥分配和数字签名问题  使用一对密钥，公开密钥和私有密钥  公开密钥对其他人个公开  私有密钥只有自己知道 2011 ©谷安天下版权所有 公钥密码学简介 2011 ©谷安天下版权所有 公钥密码学简介 公钥密码学的特点：  很容易通过计算得到一对密钥（公钥：私钥）  由公钥和明文很容易计算出密文  由私钥和明文很容易计算出签名  由私钥和密文很容易计算出明文  敌手只有公钥，不能通过计算获得私钥  敌手只有公钥和密文，不能通过计算获得明文 2011 ©谷安天下版权所有 目录 公钥密码学简介  公钥密码学基本原理 公钥密码学的应用 软件实现公钥算法的要点 2011 ©谷安天下版权所有 公钥密码学基本原理 现代公钥密码学基于3大数学难题：  大整数的素因子分解  有限域内的离散对数求解  椭圆曲线上的离散对数求解 2011 ©谷安天下版权所有 公钥密码学基本原理 大整数的素因子分解： 选取两个大素数（质数）p和q，160bits以上，计算n = p * q，销毁p和q， 逆向分解 n 为 p 和 q“很难”。

NP复杂度问题 基于两个定理：  正整数内素数有无穷多个 x 越大，小于 x 的素数越多，当 x 很大时，小于 x 的素数个数约等于 x/lnx 最新成果： 量子计算机求解大整数素因子分解是P问题 2011 ©谷安天下版权所有 RSA • 欧拉φ函数（Euler’s totient function） – 欧拉函数φ(n)：表示小于 n 且与 n 互素互素的正整数的个 数； – 欧拉函数的性质： • 对任意素数 p，有 φ(p) = p – 1； • 对任意两个素数 p、q，则对 n = pq 有： φ(n) = φ(pq) = φ(p)φ(q) = (p–1)(q–1) 2011 ©谷安天下版权所有 RSA 欧拉定理 如a 和 n 是互素的整数，则有： 等价形式： n) a n (mod 1 ) ( ≡ φ n) a n (mod a )+1 ( ≡ φ 2011 ©谷安天下版权所有 RSA • RSA算法要求： M = Med mod n • 欧拉定理推论： – 有两个素数 p 和 q, 令 n = pq , 对任意整数 k 和 m (0 1 用户的私有密钥x必须是一个1~ (p- l) 之间的随机数或伪随机数（即1 #include #define CEILINGOFPRIMES 0xffffffff #define MAXPRIMESNUM 24580//24580(the number of primes between 0 and sqr(2^32)) #define MAXFACTORBASE 669//a factor base less than 5000 #define STARTINTEGER 5000 2011 ©谷安天下版权所有 实现大素数 class CPrimeNumber : public CBigInteger { protected: CDRBG *drbg; CHash *hash; string status; static bool full_primes;//indicates whether primes_table is full static word16 primes_table[MAXPRIMESNUM]; static word16 ptlen;//primes_table length protected: bool JudgePrimesBitsForRSA(bool p, word16 L, word16 N1, word16 N2); void GeneratePrimesTable(word32 u); bool Shawe_Taylor_Random_Prime(const word16 length, const CBigInteger bool TrialDivision(CBigInteger void SieveProcedure(word32 u); 2011 ©谷安天下版权所有 实现大素数 public: CPrimeNumber(CDRBG *pDrbg=0, CHash *pHash=0); CPrimeNumber(CDRBG *pDrbg=0, CHash *pHash=0, word8 value[], word16 size = 0, bool sign = 0):CBigInteger(value, size, sign ); CPrimeNumber(const CPrimeNumber CPrimeNumber CBigInteger GetPrimeNumber(); bool WritePrimesTable(ofstream bool ReadPrimesTable(ifstream void InitializePrimestable(); bool Provable_Prime_Construction_for_RSA(const word16 L, const word16 N1, const word16 N2, CBigInteger }; 2011 ©谷安天下版权所有 实现大素数 public: CPrimeNumber(CDRBG *pDrbg=0, CHash *pHash=0); CPrimeNumber(CDRBG *pDrbg=0, CHash *pHash=0, word8 value[], word16 size = 0, bool sign = 0):CBigInteger(value, size, sign ); CPrimeNumber(const CPrimeNumber CPrimeNumber CBigInteger GetPrimeNumber(); bool WritePrimesTable(ofstream bool ReadPrimesTable(ifstream void InitializePrimestable(); bool Provable_Prime_Construction_for_RSA(const word16 L, const word16 N1, const word16 N2, CBigInteger }; 2011 ©谷安天下版权所有 软件实现公钥算法的其它要点  遵守强制性的密钥管理流程  密钥管理模块不允许插入调试后门  谨慎使用第三方组件 需要保密的材料应完全控制其生成、存放、销毁路径，杜绝不经意的隐蔽通道导致机密数的泄露，进而影响密钥安全。

好的原则是：机密材料最后使用后就地销毁 2011 ©谷安天下版权所有 总结  密码学的理论成果是及其丰富的  社会在小心翼翼的把密码学用于实践  密码学的协议成果将更多的应用  电子商务、云计算、信息化的蓬勃发展带来更多的密码学应用机会 例如，PKI建设、数字现金、电子选举、秘密共享等等， 设想一下，如果连支票也采用数字形式，其带来的安全问题和冲击是 多么的大能解决这些问题只有密码学 2011 ©谷安天下版权所有 。