๋น…๋„˜์—ฐ์‚ฐ 1

์ˆ˜ํ•™ ๋น…๋„˜ ์—ฐ์‚ฐ์—์„œ LCM( P-1, Q-1) ๊ฐ’ ๊ตฌํ•˜๋Š” ๋ฒ•

LCM์€ ๋‘์ˆ˜์˜ ์ตœ์†Œ ๊ณต๋ฐฐ์ˆ˜ ์ด๋‹ค. ์ด๊ฑด ๊ฐ„๋‹จํ•œ ์‚ฐ์ˆ˜ ์ด์ง€๋งŒ ์‹ค์ œ๋กœ ์ ์šฉํ• ๋•Œ๋Š” ์–ด๋ ค์›Œ ๋ณด์—ฌ์„œ ํ•œ๋ฒˆ ์ •๋ฆฌํ•œ๋‹คRSA ์•”ํ˜ธ์—์„œ ์†Œ์ˆ˜ P์™€ Q๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ๊ฐœ์ธํ‚ค D๋ฅผ ๊ตฌํ•  ๋•Œ,P−1๊ณผ Q−1์˜ ์ตœ์†Œ๊ณต๋ฐฐ์ˆ˜(LCM)์„ ์ด์šฉํ•œ๋‹ค.๋น…๋„˜ ์—ฐ์‚ฐ์„ ํ• ๋•Œ ์•„๋ž˜ ๊ณต์‹์„ ์ด์šฉํ•˜์—ฌ ๊ณ„์‚ฐ ํ•œ๋‹ค$$ LCM(P-1,Q-1) = \frac { (P-1) \times (Q-1) } { GCD( P-1, Q-1) } $$์—ฌ๊ธฐ์„œ:P์™€ Q๋Š” ๋‘ ๊ฐœ์˜ ์†Œ์ˆ˜์ž…๋‹ˆ๋‹ค.P−1๊ณผ Q−1์€ ๊ฐ๊ฐ P์™€ Q์—์„œ 1์„ ๋บ€ ๊ฐ’์ž…๋‹ˆ๋‹ค.GCD(P−1,Q−1) ๋Š” P-1๊ณผ Q-1 ์˜ ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜(Greatest Common Divisor)๋ฅผ ์˜๋ฏธํ•œ๋‹ค.์˜ˆ๋ฅผ ๋“ค์–ด, P=11, Q=7์ผ ๋•Œ:P−1=10, Q−1=6GCD(10,6) = 2 (์ตœ๋Œ€๊ณต์•ฝ์ˆ˜)LCM(10,6) = (..

PKI/Cryptography 2024.10.16
๋ฐ˜์‘ํ˜•