RSA 暗号は、今日日の(ネットワーク)セキュリティまわりの分野で、広く使われている技術だと思っています。
例えば RSA2048 では、「MSB が 2048 bit 目になるような、ただ二つの素数 p, q に素因数分解できるような合成数を、ランダムに生成する」必要があります。
これはちょっと考えて、どうやったらこれが実現できるのかが自明ではないな、と思いました。
質問
今ある RSA の実装は、どのように実行可能な時間の中で、上記性質を見たす素数のペアを生成しているのでしょうか?
RSA 暗号は、今日日の(ネットワーク)セキュリティまわりの分野で、広く使われている技術だと思っています。
例えば RSA2048 では、「MSB が 2048 bit 目になるような、ただ二つの素数 p, q に素因数分解できるような合成数を、ランダムに生成する」必要があります。
これはちょっと考えて、どうやったらこれが実現できるのかが自明ではないな、と思いました。
今ある RSA の実装は、どのように実行可能な時間の中で、上記性質を見たす素数のペアを生成しているのでしょうか?
Fumu7 さんや metropolis さんの回答を参考に、ランダムに奇数を生成した後、 miller rabin のテストを実施しているのだ、という理解を得ました。
miller rabin のテストは、1回の試行で対象が3/4以上の確率で素数であることを判定するアルゴリズムで、これを繰り返し実行して実用上問題ないぐらいの確率までテストを繰り返しているのだ、という理解です。
参考として、その動作する miller-rabin の具体的コードを以下に載せておきます。 (bitint-crypto-utils を利用しています)
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>