2021. 9. 22. 17:07ใBACKEND/Security
***************** INDEX *****************
๐พ ๋ชจ๋์ฐ์ฐ
๐ค Chinese Remainder Theorem
********************************************
๋ชจ๋์ฐ์ฐ
์ํธํ์์ ๋น ์ง ์ ์๋ ๋ชจ๋์ฐ์ฐ์ ๊ธฐ๋ณธ์ผ๋ก ์ํธํ์์ ์ฌ์ฉํ๋ ์ํ์ ์ธ ๊ธฐ๋ฒ๋ค์ ์์๋ณด๊ณ ์ ํฉ๋๋ค.
์ด ํฌ์คํ ์ ๋ชจ๋์ฐ์ฐ์ ๊ธฐ๋ณธ์ ์ผ๋ก ์๊ณ ์๋ค๋ ๊ฐ์ ํ์ ์์ฑํ๊ฒ ์ง๋ง,
๊ทธ๋๋ ๋ชจ๋์ฐ์ฐ์ ๊ฐ๋ณ๊ฒ ํ๊ณ ๋ง ๊ฐ๊ฒ ์ต๋๋ค.
๋ชจ๋์ฐ์ฐ?
๋๋์ ์ ํด์ ๋๋จธ์ง๋ฅผ ๊ตฌํ๋ ์ฐ์ฐ. ๋ฐ๋์ด ํ๋๋ฐ์ ์๋ ์๊ณ์ฐ์ฐ
AmodB=C
๋ชจ๋์ฐ์ฐ์์ ๊ธฐ๋ณธ์ ์ผ๋ก B๊ฐ ๋์ผํ๋ฉด ํฉ์ฐ ๊ฐ๋ฅํฉ๋๋ค.
ex) (2mod5)+(4mod5)=(2+4)mod5=1
โ๏ธ ๋ชจ๋์ ๊ฑฐ๋ญ์ ๊ณฑ
๋ชจ๋ ์ฐ์ฐ์ ๊ฑฐ๋ญ์ ๊ณฑ์ ๊ณ์ฐํ ๋์๋ ์์ฃผ ์ค์ํ ํน์ง์ ์ธ๊ธํ ์ ์๋๋ฐ์.
๊ณ์ฐ ๋์ค์ mod๋ฅผ ์ทจํด๋ ๊ฐ์ ๊ฒฐ๊ณผ๊ฐ ๋์จ๋ค๋ ๊ต์ฅํ ํธ๋ฆฌํ ํน์ง์ด ์์ต๋๋ค.
์์๋ฅผ ํตํด ์ดํด๋ฅผ ๋์๋ณผ๊ฒ์.
64mod11=(6ร6mod11)ร(6ร6mod11)=(36mod11)ร(36mod11)=(3ร3)mod11=9
์์๋ฅผ ๋ณด๋ ์ดํด๊ฐ ์ฝ๊ฒ ๊ฐ์๋์? (์ดํด ๊ฐ์ํ๋ ๊ฒ ๊ฐ๋ค์,,ใ ใ ,ใ ใ ,,,)
์ ๊ณฑ์ ๋๋ ๊ณ์ฐํ๊ธฐ ํธํ๊ฒ ์ชผ๊ฐ๋์ ๋ค์ ์์ ์๋ฅผ ๋ค๋ฃจ๋ ๋ฐฉ๋ฒ์ ๋๋ค.
์์๋ก๋ 64์ด๋ผ๋ ์์ ์์ง๋ง, 6243์ด๋ผ๋ ์๋ฅผ ๊ณ์ฐํ ๋์๋ ๊ต์ฅํ ์ ์ฉํ๊ฒ ์ฃ ?
โ๏ธ ๋ชจ๋์ ๊ณฑ์ ์ ์ญ์
์ด๋ฒ ํฌ์คํ ์ ๋ง์ง๋ง ์น์ ์ธ CRT(์ค๊ตญ์ธ์ ๋๋จธ์ง ์ ๋ฆฌ)๋ฅผ ์ ๋ฆฌํ ๋ ํ์๋ก ์์์ผํ๋ ๊ฐ๋ ์ ๋๋ค.
๋จผ์ , ๊ณฑ์ ์ ์ญ์์ด๋ผ๊ณ ํ๋ฉด ์ด๋ค ์๋ฅผ ๊ณฑํ์ ๋ 1์ด ๋๋ ์์ฃ .
(x๊ฐ 3์ผ ๋, x์ ๊ณฑ์ ์ ์ญ์์ 13์ด์ฃ .)
๋ชจ๋๊ณ์ฐ์์ ๊ณฑ์ ์ ์ญ์์ ์ด๋ป๊ฒ ์ฐพ์๊น์?
๋ชจ๋ 12 ์์์ 7์ ๊ณฑ์ ์ ์ญ์ x๋ฅผ ๊ตฌํ ๋์ ์์ (7รx)mod12=1 ์ผ๋ก ์ ์ํ ์ ์์ต๋๋ค.
์ํธํ - ์ํ์ ๋ฌธ์
์ด์ฐ๋์๋ฌธ์
Y=Xn ๋ผ๋ ์์์ X๊ฐ์ด ์ฃผ์ด์ง ๋ Y๊ฐ์ ์ฝ๊ฒ ๊ตฌํ ์ ์์ง๋ง(๋จ์๊ฐ์ ๊ฐ๋ฅ),
Y ๊ฐ์ด ์ฃผ์ด์ง ๋ X๊ฐ์ ๊ตฌํ๊ธฐ ์ด๋ ต๋ค(๊ต์ฅํ ๊ธด ์๊ฐ์ด ํ์)๋ ์๋ฆฌ์ ๋๋ค.
๋ชจ๋ ์์์ ์ ๊ณฑ๊ทผ์ ๊ตฌํ๋ ๋ฌธ์ ๋ก ๋ค์ํ ์ํธํ ๋ฐฉ์์ ๊ธฐ์ด๊ฐ ๋๋ ์์ฃผ ์ค์ํ ๊ฐ๋ ์ ๋๋ค.
๋ชจ๋๋ก ์ฌ์ฉ๋๋ ์ซ์๊ฐ ๋งค์ฐ ํฌ๋ฉด ์ด์ฐ๋์ ๊ณ์ฐ์ด ๋งค์ฐ ์ด๋ ต๊ณ ์๊ฐ์ด ๋๋จํ ๋ง์ด ๊ฑธ๋ฆฌ๊ธฐ ๋๋ฌธ์ ํด๊ฒฐํ๊ธฐ ์ด๋ ต์ต๋๋ค.
์ด๋ฐ ํน์ง์ ์ด์ฉํ์ฌ Diffie-Hellman์ ๊ณต๊ฐํค ์ํธ ์๊ณ ๋ฆฌ์ฆ์ ์ค๊ณํ์ต๋๋ค.
์์ธ์ ๋ถํด ๋ฌธ์
Integer factorization Problem.
๋งค์ฐ ํฐ ์ ์๋ฅผ ์์ธ์ํด์ผํ๋ ๋ฌธ์ ์ ๋๋ค.
๋ ์๋ฅผ ๊ณฑํ๋ ์ฐ์ฐ์ ์ฝ์ง๋ง, ๊ณฑํด์ง ์๋ฅผ ๋ ์๋ก ์ชผ๊ฐ๋ ๊ฑด ์ด๋ ต์ต๋๋ค.
Chinese Remainder Theorem
โ๏ธ ์ค๊ตญ์ธ์ ๋๋จธ์ง ์ ๋ฆฌ (CRT)
์ค๊ตญ์ธ์ ๋๋จธ์ง ์ ๋ฆฌ์ ๋ํด ์์๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค.
CRT์ ์ ์๋ ์๋์ ๊ฐ์ต๋๋ค.
K๊ฐ์ ์๋ก์: m1,m2,m3,ยทยทยท,mk (์ฆ, gcd(mi,mj)=1,iโ j )์
์ ์ a1,a2,a3,ยทยทยท,ak์ ๋ํด
๋ค์ ์ฐ๋ฆฝ ๋ฐฉ์ ์์ ๋ง์กฑํ๋ x๋ mod(m1รm2รยทยทยทรmk)์ ๋ํด ์ ์ผํ ํด๋ฅผ ๊ฐ์ง๋ค.
{xโกa1(modm1)xโกa2(modm2)โฎxโกak(modmk)
์์ ์ฐ๋ฆฝ ๋ฐฉ์ ์์์ ํ๋์ ํด๊ฐ ๋์จ๋ค๋ ๊ฒ์ด CRTํต์ฌ์ ๋๋ค.
๋ญ๊ฐ ํ์ด ์ค๋ช ํ๋ ๋ฒ๋ฆ์ด ์๋๋ฐ, ์ด ํฌ์คํ ์ ์ค๋ช ์ ํ ๊ฒ ์๋ค์ ...
์ต๋ํ ์์์ด๋ผ๋,,ใ ใ ์ ์จ๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค.
๋จ์ผ ํด x๋ฅผ ๊ตฌํ๋ ๊ณผ์ ์ ์๋์ ๊ฐ์ต๋๋ค.
1. M=m1รm2รm3รยทยทยทรmk
2. M1=Mm1,M2=Mm2,ยทยทยท,Mk=Mmk
3. Mโ11=Mโ11(modm2), Mโ12=Mโ12(modm2),ยทยทยท,Mโ1k=Mโ1k(modmk)
4. x=(a1รM1รMโ11+a2รM2รMโ12+ยทยทยท+akรMkรMโ1k)modM
๊ณ์ฐ์์ด ๊ต์ฅํ ๋ณต์กํด๋ณด์ด์ฃ . ํ์ด๋ณด๋๊น ์ค์ ๋ก๋ ๋ณต์กํ ๊ฒ ๊ฐ์์...ใ ใ ใ .,..
๊ทธ๋๋ ๋ช ๋ฒ ํด๋ณด๋ฉด ์ต์ํด์ง๊ฒ ์ฃ ?
์์๋ฅผ ๊ฐ์ด ํ๋ฉด์ ์ดํด๋ฅผ ๋๋๋ก ํด๋ด ์๋ค.
ex ) xโก2 (mod5), xโก3 (mod5), xโก2 (mod7) ๋ฅผ ๋ชจ๋ ๋ง์กฑํ๋ x?
1. ๋ชจ๋ ์๋ก์๋ฅผ ๊ณฑํ์ฌ M ๊ตฌํ๊ธฐ
M=m1รm2รm3รยทยทยทรmk ๐๐ป M=3ร5ร7=105
2. M1,M2,M3 ๊ณ์ฐํ๊ธฐ
M1=Mm1,M2=Mm2,ยทยทยท,Mk=Mmk ๐๐ป M1=5ร7, M2=3ร7, M3=3ร5
3. Mโ1k ๊ณฑ์ ์ ์ญ์ ๊ตฌํ๊ธฐ
Mโ11=Mโ11(modm2), Mโ12=Mโ12(modm2),ยทยทยท,Mโ1k=Mโ1k(modmk)
๋ชจ๋ ์ฐ์ฐ์ ๊ณฑ์ ์ ์ญ์์ ์ ์ M1รMโ11(modm)=1 ๋ฅผ ์ด์ฉํ์ฌ ์์ ์์์ ํ ์ ์์ต๋๋ค.
๐๐ป {xโกa1(modm1) ยทยทยท 35โ1(mod3)=1, x=2xโกa2(modm2) ยทยทยท 21โ1(mod5)=1, x=1xโกa3(modm3) ยทยทยท 15โ1(mod7)=1, x=1
๋ชจ๋์ฐ์ฐ์ ๊ณฑ์ ์ ์ญ์์ ๊ตฌํ๋ ๊ฒ์ด ์ด์ํ ์ ์์ผ๋, ํ๋๋ง ๊ฐ์ด ํ์ด๋ด ์๋ค ~!
35โ1(mod3)=1
35รMโ1 (mod3)โก2รMโ1 (mod3)=1,Mโ1โ{2,5,8,ยทยทยท}
โดMโ1=2
์ฌ๊ธฐ๊น์ง ์ ๋ฐ๋ผ์ค๊ณ ๊ณ์ ๊ฐ์ ..
์, ์ด์ ๋ง์ง๋ง์ ๋๋ค.
4. x๊ฐ ์ฐพ๊ธฐ
x=(a1รM1รMโ11+a2รM2รMโ12+ยทยทยท+akรMkรMโ1k)modM ๋ฅผ ๋ง์กฑํ๋ x๊ฐ ์ฐพ์๋ด ์๋ค.
x=((2ร35ร35โ1mod3)+(3ร21ร21โ1mod5)+(2ร15ร15โ1mod7))mod105
=((2ร35ร2)+(3ร21ร1)+(2ร15ร1))mod105
=23
์ถ๊ฐ์ ์ผ๋ก, 4๋ฒ๊ณผ ๊ฐ์ ๊ฒฐ๋ก ์ด ๋์ค๋ ์ด์ ๋ x๊ฐ์ ์ฐพ์ ๋ ์ ์ฒด ์์์ modm1์ ํ๊ฒ ๋๋ฉด
์ฒซ ๋ฒ์งธ ๊ณฑ์ ์ ์ ์ธํ ๋๋จธ์ง๋ m1์ ํฌํจํ๊ณ ์๊ธฐ ๋๋ฌธ์ (2๋ฒ์งธ ๋จ๊ณ ์ฐธ์กฐ) 0์ผ๋ก ์ฒ๋ฆฌ๋ฉ๋๋ค.
๋ฐ๋ผ์ ์ฐ๋ฆฝ๋ฐฉ์ ์์ ์ฒซ ๋ฒ์งธ์ ๋์ผํ ์์ด ๋์ค๊ฒ ๋์ฃ .
'BACKEND > Security' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
RSA, ์ ๋๋ก ์ดํดํ๊ธฐ (1) (4) | 2021.10.14 |
---|---|
PRNG, ์ ๋๋ก ์ดํดํ๊ธฐ (6) | 2021.09.16 |
Backend Software Engineer
๐๐ฎ๐ง ยท ๐๐ฎ๐๐ค๐ฃ๐๐จ๐ช๐ฃ ๐๐๐ง๐