์ƒˆ์†Œ์‹

์ธ๊ธฐ ๊ฒ€์ƒ‰์–ด

๐Ÿ“  Secure/๐Ÿ†” Crypto

[Crypto] RSA ๋ณตํ˜ธํ™” ์ฆ๋ช… ( ์žฌ์ •๋ฆฌ ๅฟ… )

  • -
๋ฐ˜์‘ํ˜•

RSA ํ‚ค ํ˜•์„ฑ

- ๋‘ ์†Œ์ˆ˜ p,q๋ฅผ ๊ณจ๋ผ์„œ n=pq๋กœ ๋†“๋Š”๋‹ค.

- e๋ฅผ gcd(phi(n),e) = 1์ด ๋˜๋„๋ก ๋ฝ‘๋Š”๋‹ค. phi๋Š” ์˜ค์ผ๋Ÿฌ totient ํ•จ์ˆ˜

- d= $e^-1$ mod phi(n)์„ ๊ณ„์‚ฐํ•œ๋‹ค. modular inverse๋Š” e์˜ ์„ ํƒ์— ์˜ํ•ด ์–ธ์ œ๋‚˜ ์กด์žฌํ•˜๊ณ , ํ™•์žฅ๋œ ์œ ํด๋ฆฌ๋“œ ํ˜ธ์ œ๋ฒ•์„ ์ด์šฉํ•ด ๋น ๋ฅธ ์‹œ๊ฐ„์•ˆ์— ๊ณ„์‚ฐ ๊ฐ€๋Šฅ

 

p, q = ๋ฌด์ž‘์œ„๋กœ ํฐ ๋‘ ์†Œ์ˆ˜

n = pq

phi = (p-1)*(q-1) >> n์ดํ•˜์˜ n๊ณผ ์„œ๋กœ์†Œ์ธ ์ˆ˜๋“ค์˜ ๊ฐœ์ˆ˜

e = ์ฃผ๋กœ 65537 , ๋‹ค๋ฅธ ๊ฐ’์ด ๋˜๋”๋ผ๋„ 1<e<phi์ด๊ณ  phi์™€ ์„œ๋กœ์†Œ์ธ ์ˆ˜๋กœ ์„ ํƒ

d = mod phi์— ๋Œ€ํ•œ e์˜ ๊ณฑ์…ˆ ์—ญ์›์„ ๊ตฌํ•œ๋‹ค. de = 1+k(phi)

 

์•”ํ˜ธ๋ฌธ c๋ฅผ ๋ณตํ˜ธํ™” ํ•˜๋Š” ํ•จ์ˆ˜๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค ( D=๋ณตํ˜ธํ™” )

D(c) = $c^d$ mod n ์‹ค์ œ๋กœ ํ‰๋ฌธ์„ ์•”ํ˜ธํ™”ํ–ˆ๋‹ค๊ฐ€ ๋ณตํ˜ธํ™”ํ•˜๋ฉด ๋ณต๊ตฌ ๊ฐ€๋Šฅํ•˜๋‹ค๋Š” ๊ฒƒ์„ ๋ณด์ผ ์ˆ˜ ์žˆ๋‹ค.

D(E(m)) = E$(m)^d$ mod n

              = $m^{ed}$ mod n
              = $m^{kphi(n)+1}$ mod n

gcd(m,n)=1 ์ผ ๊ฒฝ์šฐ

gcd์˜ ์›๋ฆฌ ( gcd = ๋‘ ์ˆ˜ ์‚ฌ์ด์— ์กด์žฌํ•˜๋Š” ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜๋ฅผ ์ฐพ๋Š” ์œ ํด๋ฆฌ๋“œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ )
- ์ž„์˜์˜ ๋‘ ์ž์—ฐ์ˆ˜ a,b๊ฐ€ ์ฃผ์–ด์กŒ์„๋•Œ a>b๋ผ๊ณ  ๊ฐ€์ •
- a๋ฅผ b๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ n์ด๋ผ๊ณ  ํ•˜๋ฉด ( a % b = n )
- n์ด 0์ผ๋•Œ, b๊ฐ€ ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜(GCD)
- n์ด 0์ด ์•„๋‹ˆ๋ผ๋ฉด a์— b๊ฐ’์„ ๋‹ค์‹œ ๋„ฃ๊ณ  n์„ b์— ๋Œ€์ž… ํ›„ step2๋ถ€ํ„ฐ ๋ฐ˜๋ณต

์˜ค์ผ๋Ÿฌ์˜ toitient ์ •๋ฆฌ์— ์˜ํ•ด $m^{phi(n)}$=1 mod n ์ด๋ฏ€๋กœ D(E(m))= m mod n์ด๋‹ค.

์˜ค์ผ๋Ÿฌ์˜ ํ† ์…˜ํŠธ ํ•จ์ˆ˜๋Š” ๋ชจ๋“ˆ๋Ÿฌ ๊ณฑ์…ˆ ์—ญ์›์ด ์กด์žฌํ•˜๋Š” ์ˆ˜์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ•จ์ˆ˜ ฯ• ๊ธฐํ˜ธ๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค.
์ž„์˜์˜ ์–‘์˜ ์ •์ˆ˜ n์— ๋Œ€ํ•ด ฯ•(n)์€ n ์ดํ•˜์˜ ์–‘์˜ ์ •์ˆ˜ ์ค‘ n ๊ณผ ์„œ๋กœ์†Œ์ธ ๊ฒƒ์˜ ๊ฐœ์ˆ˜์™€ ๊ฐ™๋‹ค.
์˜ค์ผ๋Ÿฌ ํ”ผ(ํŒŒ์ด) ํ•จ์ˆ˜๋ผ๊ณ ๋„ ํ•œ๋‹ค.

gcd(m,n) !=1 ์ผ ๊ฒฝ์šฐ n=pq์ด๋ฏ€๋กœ gcd(m,n)์€ p๋˜๋Š” q์ด๋‹ค.

์ผ๋ฐ˜์„ฑ์„ ์œ„ํ•ด gcd(m,n) = p๋กœ ๋†“๋Š”๋‹ค.

์ผ๋‹จ $m^{ed}$ mod p = 0์ด๊ณ , m mod p = 0์ด๋ฏ€๋กœ  m=D(E(m)) mod p ์ด๋‹ค.

(m,q) =1์ด๋ฏ€๋กœ ํŽ˜๋ฅด๋งˆ์˜ ์†Œ์ •๋ฆฌ์— ์˜ํ•ด $m^{q-1}$ = 1 mod q ์ด๋‹ค.

ํŽ˜๋ฅด๋งˆ์˜ ์†Œ์ •๋ฆฌ
a๊ฐ€ ์ •์ˆ˜์ด๊ณ  p๊ฐ€ ์†Œ์ˆ˜์ด๊ณ  a๊ฐ€ ์ž„์˜์˜ ์†Œ์ˆ˜ p์˜ ์•ฝ์ˆ˜๊ฐ€ ์•„๋‹๋•Œ
$a^p$=a(mod p )์ด๋ฉฐ a๊ฐ€ 0์ด ์•„๋‹๋•Œ
$a^{p-1}$ = 1 (mod p) ์ด๋‹ค.

๋”ฐ๋ผ์„œ D(E(m)) = $m^{kphi(pq)+1}$ = $m^{k(p-1)(q-1)+1}$ = $(m^{q-1})^{k(p-1)}$m = m mod q ์ด๋‹ค.

๋”ฐ๋ผ์„œ ๋‚˜๋จธ์ง€ ์ •๋ฆฌ์— ์˜ํ•ด D(E(m)) = m mod n ์ด๋‹ค.

 

๋ฐ˜์‘ํ˜•
Contents

ํฌ์ŠคํŒ… ์ฃผ์†Œ๋ฅผ ๋ณต์‚ฌํ–ˆ์Šต๋‹ˆ๋‹ค

์ด ๊ธ€์ด ๋„์›€์ด ๋˜์—ˆ๋‹ค๋ฉด ๊ณต๊ฐ ๋ถ€ํƒ๋“œ๋ฆฝ๋‹ˆ๋‹ค.