2. Math of cryptography (2)

1. Extended Euclid Algorithm

given Integer a, b >0

find intetger s and t such that

sa + tb = gcd(a,b)

ex) a= 161, b =29

gcd(a,b) =7

s=-1 , t= 6

-1*161 + 6*28 = 7

---

r1 <- a, r2 <-b

s1 <- 1, s2 <- 0

t1 <- 0, t2 <- 1

while(r2 >0)

    q <- r1/r2

    r  <- r1 -q*r2

    r1 <- r2, r2 <- r

    s<-s1-q*s2

    s1<-s2, s2<-s

    t  <-t1 - q*t2

    t1 <- t2, t2 <- t

gcd<-r1, s<-s1, t<-t1

q	r1	r2	r	s1	s2	s	t1	t2	t
5	161	28	21	1	0	1	0	1	-5
1	28	21	7	0	1	-1	1	-5	6
3	21	7	0	1	-1	4	-5	6	-23
	7(GCD)	0 (r2)		-1(s)	4		6(t)	-23

원리 s와 t에대해 아래식이 성립해서 가능한 것 

s1a + t1b = r1

s2a + t2b = r2

-증명 

파일이 앞에 있을때 (while 조건문 위치) 아래식이 성립하는것은 자명

s1a + t1b = r1

s2a + t2b = r2

위 식이 항상 성립 임을 보이자

r1,r2 -> r2, r1-qr2

s1,s2 -> s2,s1-qs2

t1,t2 -> t2, t1 -qt2

->

s2a +t2b = r2 성립

(s1 - qs2)a + (t1 - qt2)b

=s1a - qs2a + t1b - qt2b

=s1a + t1b - q(s2a+t2b)

=r1 + q * r2

---

2. Modular Algorithm

a / n

a = qn +r ( r≥0)

n은 양의 정수

a mod n (a % n ) = r

27 mod 5 =2

-18 mod 14 = 10

잉여류

모듈로 n을 이용하는 모듈로 연산의 결과는 항상 0~n-1의 정수 값

• 0≤ a mod n ≤ n-1

Zn = {0, 1, ... ,n-1} : r이 될 수 있는 값들의 범위

Z->a

  ->b

( a + b ) mod n

( a - b ) mod n 

( a * b ) mod n 

 

(14 + 7) mod 15 = 6

( 7 - 11) mod 13 = 9

( 7*11 ) mod 20 = 17

property (+,-,*)

(a ? b) mod n = ( a mod n ? b mod n ) mod n

위의 세가지 연산에 대해 위 성질이 성립한다.

( 1,723,345 * 2,124,945 ) mod 11

= ( 8 * 9 ) mod 11

= 6

6371이 3의 배수?

<-> 6+3+7+1 이 3의 배수?

∵ 6371 mod 3= (6*10^3 + 3*10^2 + 7*10^1 + 1 * 10^0)mod 3  

                      = (6+3+7+1) mod 3 (∵10^n mod 3 = 1)

배수판별 

4의 배수? 뒤에 두 자리만 본다

2345678 mod 4 = (2345600 + 78) mod 4

                          = 78 mod 4

mod가 중요한이유 

암호학에서 실수는 암호화와 복화화 하는 과정에서 정보 손실이 발생할 수 있으므로, 정수만 사용한다.

또한, 양의 정수의 크기(n)가 매우 커지게 될때, Zn의 범위가 커지게 되고 그 내부에서 가감승제를 하기 위해 mod 연산이 중요하다.