Processing math: 100%

CRT, Modulo Operation

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' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€