Diffie-Hellman 密钥交换算法中大素数 p 及其本原根 g 的求法

求一个大素数 p 很容易,用现成的素性验证算法就可以了。不过已知一个素数 p,求其本原根则很困难,因为需要将 p - 1 的素因子 q1,q2,……qk-1,qk都找出来,然后分别验证 gq1 mod p, gq2 mod p, ……gqk-1 mod p, gqk mod p,如果都不等于 1,则 g 是 p 的一个本原根。而然,如果 p 是一个很大的素数,例如 128 个 2 进制位的素数,要分解出 p - 1 的所有素因子来则是一件很困难的事情。

难道没有办法快速求一个大素数 p 及其本原根 g 的方法吗?方法肯定是有的,不然 Diffie-Hellman 算法也就没有意义了。下面就给出一个快速求大素数 p 及其本原根的算法,并给出相应的 php 的程序。

算法如下:

P1. 利用素性验证算法,生成一个大素数 q;
P2. 令 p = q * 2 + 1;
P3. 利用素性验证算法,验证 p 是否是素数,如果 p 是合数,则跳转到 P1;
P4. 生成一个随机数 g,1 < g < p - 1;
P5. 验证 g2 mod p 和 gq mod p 都不等于 1,否则跳转到 P4;
P6. g 是大素数 p 的本原根。

生成一个 128 位的素数 p 和它的一个小于 128 位的本原根 g 的程序如下(需要 big_int 扩展):

getdhpg.php
  1. <?php
  2.     $f = false;
  3.     $n1 = bi_from_str("1");
  4.     $n2 = bi_from_str("2");
  5.     while (!$f) {
  6.         // P1.  利用素性验证算法,生成一个大素数 q;
  7.         $q = bi_next_prime(bi_set_bit(bi_rand(127), 126));
  8.         // P2.  令 p = q * 2 + 1;
  9.         $p = bi_set_bit(bi_lshift($q, 1), 0);
  10.         // P3.  利用素性验证算法,验证 p 是否是素数,如果 p 是合数,则跳转到 P1;
  11.         if (bi_is_prime($p)) $f = true;
  12.     }
  13.     while ($f) {
  14.         // P4.  生成一个随机数 g,1 < g < p - 1;
  15.         $g = bi_rand(127);
  16.         // P5.  验证 g^2 mod p 和 g^q mod p 都不等于 1,否则跳转到 P4;
  17.         if ((bi_powmod($g, $n2, $p) <> $n1) and
  18.             (bi_powmod($g, $q, $p) <> $n1)) {
  19.             $f = false;
  20.         }
  21.     }
  22.     // P6.  g 是大素数 p 的本原根。
  23.     echo bi_to_str($p)."\n";
  24.     echo bi_to_str($g)."\n";
  25. ?>

标签: PHP, Cryptology

« 上一篇 | 下一篇 »

只显示10条记录相关文章

1 条回复至 "Diffie-Hellman 密钥交换算法中大素数 p 及其本原根 g 的求法" 的评论

bi_from_str
定义在哪儿呀

由 treert 于 2012-07-25 21:12:09 提交#1


发表评论

评论 (必须):