[Crypto] RSA ํ์ด์ฌ ์ฝ๋ ๋ฐ ๊ฐ๋
RSA ๊ณต๊ฐํค ๊ฐ์ธํค ๊ตฌํ๋๋ฒ
1. p ๊ฐ, q๊ฐ ์์ฑ ( ๋ฌด์์๋ก ํฐ ๋ ์์๋ฅผ ์ ํ )
# ํ์ด์ฌ์์ p, q ๊ฐ์ ์์ฑํ๋ ๋ฐฉ๋ฒ
from Crypto.Util.number import getPrime
p = getPrime(1024) #1024 = 1024bit๋ฅผ ์๋ฏธ
q = getPrime(1024)
pycryptodome์ด ์ค์น๋์ด ์์ง ์์ ๊ฒฝ์ฐ
# pycryptodome ์ค์น๋์ด์์ง ์์ ์ ์ค์น๋ฒ
$ pip install pycryptodome
2. n ๊ณ์ฐ
p์ q๋ฅผ ๊ณฑํ๋ฉด n์ด ๋๋ค.
n = p * q
3. phi ๊ณ์ฐ
(p-1)๊ณผ (q-1)์ ๊ณฑํ๋ฉด phi๊ฐ ๋๋ค.
*phi = n์ดํ์ n๊ณผ ์๋ก์์ธ ์๋ค์ ๊ฐ์
phi = (p-1) * (q-1)
4. e ์ ํ
์ฃผ๋ก 65537
๋ค๋ฅธ ๊ฐ์ด ๋๋๋ผ๋ 1<e<phi์ด๊ณ phi์ ์๋ก์์ธ ์๋ก ์ ํ
5. d ๊ณ์ฐ
mod phi์ ๋ํ e์ ๊ณฑ์ ์ ์ญ์์ ๊ตฌํ๋ค.
de=1(mod phi)๋ฅผ ๋ง์กฑํ๋ d๋ฅผ ๊ณ์ฐํ๋ค.
์ฆ, ์์์ ์ ์ k์ ๋ํด์ ๋ค์์ ๋ง์กฑํ ๊ฒ
de=1+k(phi)
# gmpy2์ invert๋ divm์ผ๋ก ๊ณ์ฐํ ์ ์๋ค.
d = invert(e, phi)
d = divm(1, e, phi)
# invert = ๋ฐ๋ก ๊ณฑ์
์ ์ญ์์ ๊ตฌํด์ค๋ค
# divm = ์ฒซ๋ฒ์งธ ์ธ์๋ฅผ 1๋ก ์ง์ ํด์ฃผ๋ฉด ์ญ์์ ๊ตฌํด์ค๋ค.
gmpy2 ์ค์น๋ฒ *์ถํ ๋ด๊ฐ ์์ฑํ ๊ธ๋ก ๋ณ๊ฒฝํ ์์
https://domdom.tistory.com/169
6. ๊ฒฐ๊ณผ
๊ณต๊ฐํค: (e, n)
๊ฐ์ธํค: (d, n)
RSA ์ํธํ ๋ฐ ๋ณตํธํ
์ํธํ
์ํธ๋ฌธ = ํ๋ฌธ^e mod n
๋ณตํธํ
๋ณตํธ๋ฌธ = ์ํธ๋ฌธ^d mod n