crypto4c-ch08-数论入门.ppt

关于计算x^y％z 计算a8 % m 8次累乘：a×a×a×a×a×a×a×a % m 3次平方：((a2)2)2 % m 进一步：((a2%m)2%m)2%m 再比如a47 % m a47 ＝a32+8+4+2+1% m ＝a32a8a4a2a1% m ＝… 关于计算x^y％z.c int xymodz(int x, int y, int z) { int r=1; while (y) { if (y1) r = (r*x)%z; x = (x*x)%z; y/=2; } return r; } 快速计算 x^y％z 优化算法 技巧，如中国剩余定理 使用预先计算的/中间的结果 汇编语言 MASM、NASM 硬件芯片 CPLD、FPGA、ASIC 资质 并行 阵列、集群、分布式 x^y％z的硬件加速器 芯片产品 国家监制产品 公司商业产品 SSL加速器 Intel(R) NetStructure(TM) 7110/7115 e-Commerce Accelerator Broadcom CryptoNetX SSL Accelerator nCipher nForce Tamper-Resistant SSL Accelerator * 相信SSL加速器的主要部件是X^y%z(公钥和对称算法)＋SSL协议 7115/ CryptoNetX/ nForce 数学运算库 大数运算库 big number library OpenSSL、RSARef 欧几里德Euclid算法 X^Y%Z 找素数 推荐：RSARef / RSAEuro 小而较全 RSA、DES、MD2/5、BN、Prime、PKCS#1 / （or query-Google） BN in OpenSSL #include openssl/bn.h BIGNUM *BN_generate_prime(BIGNUM *ret, int bits,int safe, BIGNUM *add, BIGNUM *rem, void (*callback)(int, int, void *), void *cb_arg); int BN_is_prime(const BIGNUM *p, int nchecks, void (*callback)(int, int, void *), BN_CTX *ctx, void *cb_arg); int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m, BN_CTX *ctx); Resources Eric Weissteins World of Mathematics / The Largest Known Primes /largest.html Mersenne Prime Search / 术语 Terms bijection composite number Chinese remainder theorem discrete logarithm Eulers theorem Eulers totient function Fermats theorem Index order prime number primitive root 小结 密码学家首先得是数学家。 掌握基本的数论知识，对理解和使用公钥密码算法是必要的。 大数分解难题和离散对数难题是当前公钥密码学所依赖的两大基本问题。 Q A * 原版 “Cryptography and Network Security”, 4/e, by William Stallings 中译本 密码编码学与网络安全 第四版 PPT制作 林丰波 电子工业出版社 2006 - 2007 * 可查询两个数之间的素数：/~jrm/printprimes.html 也是素数：1993 1997 1999 2003 2011 比一亿大的几个素数 * （1）到2004年，已知的最大素数是2^24 036 583-1 （2）On February 18, 2005, Dr. Martin Nowak from Germany, found the new largest known prime number, 2^25,964,951-1. The prime number has 7,816,230 digits! It took more than 50 days of calculations on Dr. Nowaks 2.4 GHz Pentium 4 comput