정수론/RSA cryptosystem2 RSA cryptosystem RSA uses $d, e, n$ $n$ : RSA modulus $e$ : public key exponent (encryption number) $d$ : private key exponent (decryption number) 1. Get two (big) primes $p$ and $q$ 2. Let $n=pq$ 3. Get $e$ s.t. $o 2023. 12. 23. Computing $a^{k} \; (\mathrm{mod} \; m)$ and Solve $x^{k} \equiv b \; (\mathrm{mod} \; m)$ 1. binary expansion of $k$ $k = b_{0} \cdot 2^{0} + b_{1} \cdot 2^{1} + b_{2} \cdot 2^{2} + \cdots + b_{n} \cdot 2^{n}$ ($b_{i} = 0$ or $b_{i} = 1$) 2. succesive squaring $a^{2^{0}} \equiv a^{1} \equiv A_{0} \; (\mathrm{mod} \; m)$ $a^{2^{1}} \equiv (a^{2^{0}})^{2} \equiv (A_{0})^{2} \equiv A_{1} \; (\mathrm{mod} \; m)$ $a^{2^{2}} \equiv (a^{2^{1}})^{2} \equiv (A_{1})^{2} \equiv A_{2} \; (\mathr.. 2023. 12. 23. 이전 1 다음