72691


RSA 暗号は、今日日の(ネットワーク)セキュリティまわりの分野で、広く使われている技術だと思っています。

例えば RSA2048 では、「MSB が 2048 bit 目になるような、ただ二つの素数 p, q
に素因数分解できるような合成数を、ランダムに生成する」必要があります。

これはちょっと考えて、どうやったらこれが実現できるのかが自明ではないな、と思いました。

# 質問

今ある RSA の実装は、どのように実行可能な時間の中で、上記性質を見たす素数のペアを生成しているのでしょうか?


CC BY-SA 4.0
2020-11-21T06:09:51.143
72115
2020-12-16T08:15:19.313
754
question
アルゴリズム 暗号理論 rsa
rsa の素数のペアはどのように生成される?


Qiitaの記事 [RSAを実装する](https://qiita.com/moajo/items/0ea9043f9688b05fa39a)
が、割と平易に書かれていて判りやすいと思います(日本語なので)。


CC BY-SA 4.0
2020-11-22T02:04:32.787
72136
2020-11-22T02:04:32.787
217
72115
answer


Fumu7 さんや metropolis さんの回答を参考に、ランダムに奇数を生成した後、 miller rabin
のテストを実施しているのだ、という理解を得ました。

参考:  
[ミラー–ラビン素数判定法 -
Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E2%80%93%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95)

miller rabin
のテストは、１回の試行で対象が3/4以上の確率で素数であることを判定するアルゴリズムで、これを繰り返し実行して実用上問題ないぐらいの確率までテストを繰り返しているのだ、という理解です。

参考として、その動作する miller-rabin の具体的コードを以下に載せておきます。 ([bitint-crypto-
utils](https://www.npmjs.com/package/bigint-crypto-utils) を利用しています)

[code]

    candidate: <input type="text" id="candidate"><br>
    iterations: <input type="number" id="iteration" value="16"><br>
    <button id="button">Check Prime (Miller-Rabin)</button>
    <script type="module">
      import { randBetween, modPow } from 'https://unpkg.com/bigint-crypto-utils';
    
      const calculateSandD = (n) => {
        if (!(n % 2n)) throw new Error("n must be odd.");
        n--;
        let s = 0n;
        while(!(1n & n)) {
          n >>= 1n;
          s++;
        }
        return [s, n]
      }
    
      const millerRabin = (n, k) => {
        const nMinus1 = n - 1n;
        const [s, d] = calculateSandD(n);
        console.log(`s=${s.toString()}, d=${d.toString()}`)
    
        const iteration = (a) => {
          let x = modPow(a, d, n);
          if (x === 1n || x === nMinus1) {
            console.log(`evidence: r=0`)
            return true;
          }
          for(let i=1n; i<s; i++) {
            x = modPow(x, 2n, n)
            if (x === nMinus1) {
              console.log(`evidence: r=${i}`)
              return true;
            }
          }
          return false
        }
    
        while (k-- > 0) {
          const a = randBetween(n - 2n, 2n);
          console.log(`picked: ${a}`)
          if (!iteration(a)) return false;
        }
        return true;
      }
    
      document.getElementById("button").addEventListener("click", function () {
        const cand = BigInt(
          document.getElementById("candidate").value
        )
        const iter = document.getElementById("iteration").value
        const result = millerRabin(cand, iter);
        console.log(result ? "Probably Prime" : "Composite")
      })
    </script>
[/code]


CC BY-SA 4.0
2020-12-16T08:12:40.220
72691
2020-12-16T08:15:19.313
2020-12-16T08:15:19.313
3060
754
72115
answer