RSA, Public key, Diffie-Hellman, Hash

1.    RSA 푸는 문제

 

 

 

 

 

 

 

 

 

 

 

2.    public key가 가진 포지셔닝. 어떤 의미를 가지고 있고 현대 암호학은 왜 public key에서부터 등장하는가?

공개키가 암호학을 바꾸게 된 이유: 그 전엔 confidentiality가 거의 99%->공개키 등장->’무결성 개념 등장->디지털 서명 개념 등장

Confidentiality=데이터의 기밀을 유지하는 성질. 합법적으로 허가된 사용자만 그 데이터를 볼 수 있어야 한다.

Integrity=무결성=prevent unauthorized modification of data. 해당 데이터가 신뢰할 만한 데이터인지를 나타내는 척도. 인가된 사용자만이 해당 데이터를 변경할 수 있어야 한다.

Public key 

          Two keys

–      Sender uses recipient’s public key to encrypt

–      Recipient uses private key to decrypt

Public key(=key가 open되어 있다) -> public key를 가지고 메시지를 암호화. 이 메시지를 해독할 수 있는 사람은 private key를 가진 사람만 할 수 있다.

장점: symmetric 경우의 key를 일일이 나눠주는 것보다 부담이 적다

단점: 공개키를 제공하는 사람은 인증된 사람인가? 공개키와 주는 사람의 연결관계를 명확히 해줄 필요 있음 (=인증서가 필요, 검증할 무엇인가가 필요) but, 이것도 상호간의 trust가 필요. 우리나라에서 가장 상위 기관은 KESA

          Based on ‘trap door one way function’

–      “One way” means easy to compute in one direction, but hard to compute in other direction

–      Example: Given p and q, product N = pq easy to compute, but given N, it’s hard to find p and q

–      “Trap door” used to create key pairs

P와 q를 trap door로 사용하면 n은 구할 수 있음. 하지만, n을 주고 p,q를 찾는 것은 어려움.

3.    public key 의 2가지 알고리즘만 공부하기 (rsa와 diffie helman &public key에 대한 개념을 논하시오)

[공개키 기반 암호화 기술들 종류 4가지]

A.    Diffie-Hellman Key Exchange (1976년, 공개키 기반 암호의 개념/체계 제시)

                      i.        Discrete log problem à 사전 비밀 없이 보안키를 공유할 수 있는 최초의 실용 방안

B.     Knanpsack (Merkle, Hellman, 공개키 기반 암호의 구체적 알고리즘 제시, 1977년)

                      i.        The first proposed PKC

                     ii.        It is inscure

C.     RSA (1978년, 공개키 기반 암호 및 서명 알고리즘)

                      i.        Problem of factoring large numbers

D.    ECC(Elliptic Curve Cryptography: 1980년대 중반)

                      i.        Based on the algebraic structure of elliptic curves over finite fields

Rsa=나만 두 소수를 알고 있고, 그 곱을 공개하는 것

특징: (소인수분해) 수학을 기반으로 한 암호화 기술, 암호를 만들 수도 있고 디지털 서명을 만들 수도 있음.

N=p*q일 때, n을 안다고해도 p,q를 아는 것은 쉽지 않다.

이 복잡도가 곧 rsa의 복잡도가 됨.

N의 숫자를 키우면 rsa의 암호강도가 높아짐.

rsa암호를 뚫는 것은 불가능한 것은 아님. 어려울 뿐

단점: 메모리 관점에서 무겁다. X의 a승과 같은 계산을 많이 해서 속도가 느리다.

 

Diffie-hellman key exchange

특징: 암호화 하고자 하는 용도가 아님. symmetric한 key를 공유하는 기술일 뿐.

Public key을 제일 처음 꼭 single key로 encryption할 필요 없다라고 이론적인 제시를 함. 이 이후에 rsa를 가지고 실제 encryption할 수 있는 방안이 도출 된 것임.

Rsa와 달리 discrete log가 가지고 있는 문제, 복잡도에 근거하고 있음

ㄴ> rsa의 복잡도 “큰 수 n을 구성하는 p를 q를 찾는 것은 어렵다”

ㄴ>diffie-hellamn의 복잡도 “discrete loge”

Diffie-Hellman의 암호학적 강도는 discrete log problem에 근거:  (Not known: NP-complete)

given g, p, and g^k mod p → find k

->log를 찾는 게 어렵다는 것에 근거하고 있음.

->여기서 discrete log란? =a의 b승 을 구하라 할 때, a와 b를 알면 c라는 값이 도출이 됨. But, 큰 숫자 c를 주고 a와 b를 구하는 것은 어렵다. =>이산로그 문제: a도알고 b도 알아서 a의 b승 구하는 것은 쉽지만 그 반대는 어렵다.

->사람이 관여하지 않아도 기계가 random한 값 생성해서 algorithm에 맞게 g^ab 라는 비밀키를 비교적 쉽게 만들 수 있음

 

Diffie-hellman에서 symmetric키를 어떻게 나누어 가지는가?

Let p be prime, let g be a generator  //g,p는 공개

–      For any x Î {1,2,…,p-1} there is n s.t. x = gⁿ mod p

Alice selects secret value a   //앨리스와 밥은 각자 숫자를 생각함.

Bob selects secret value b   //앨리스와 밥은 각자 숫자를 생각함.

Alice sends g^a mod p to Bob  //공개 숫자에 내가 생각한 숫자를 취함. ex) g에 a승,

Bob sends g^b mod p to Alice  //공개 숫자에 내가 생각한 숫자를 취함. ex) g에 b승

//계산된 최종 숫자값을 서로에게 줌

Both compute shared secret g^ab mod p  //앨리스와 밥은 g의 a승(결과값 앎)에 b승, g의 b승(결과값 앎)에 a승은, 이 두개의 수는, 결과값이 똑같을 것임.

Shared secret can be used as symmetric key //이걸 비밀키로 쓰는 이유는 이 두개의 값은 앨리스와 밥밖에 모름.

[Diffie-hellman의 문제점=man-in-the-middle 어택에 취약할 수 밖에 없는 구조를 가짐]

mim어택이란=앨리스와 밥 '사이에' 트루디가 있음. 트루디가 '사이에서' 공격하는 구조

트루디가 g의 a승을 인터셉트해서 밥한테 g의 t승을 줌.

트루디가 g의 b승을 인터셉트해서 앨리스한테 g의 t승을 줌.

=>앨리스는 g의 a*t승을 함 & 밥은 g의 b*t승을 함 => 이 두 개의 값도 트루디가 알고 있음

앨리스가 아는 것: a, g의 a승, g의 t승, g의 a*t승

밥이 아는 것: b, g의 b승, g의 t승, g의 b*t승

트루디가 아는 것: g의 a승, g의 b승, g의 a*t승, g의 b*t승

=>트루디는 중간에서 암호화된 모든 것을 다 보고 풀어볼 수 있음. 이 사실을 밥과 앨리스는 모름. 아 이 값이 키로서 역할 하는 군 하고 맘.

sol)전달받은 키가 앨리스한테 온건지 트루디한테 온건지 검증 할 수 있는 무엇인가가 필요함

-서명을 도입? –g의 a승 이렇게 말고 k로 암호화해서 전달? 여러 solution을 생각해볼 수 있으나 solution을 간단하게 제시할만큼 간단한 문제는 아님. “You MUST be aware of MiM attack on Diffie-Hellman

4.    Hash- primitive의 관점 공부. 논하시오

A hash function is a reproducible method of turning some kind of data into a (relatively) small number that may serve as a digital "fingerprint" of the data=임의의 크기의 메시지 M을 입력으로 받아들여 일정한 크기의 해시값 H(M)을 출력하는 함수.

Crypto hash function h(x) design (참고: hash는 collision찾으면 깨진 것. 암호학은 key를 찾으면 깨진 것)

Compression: output length is small

One-way: given a value y it is infeasible to find an x such that h(x) = y

//y에 대하여 h(x)=y가 성립되는 x를 찾는 것이 계산적으로 불가능

No collisions // collision은 일어날 수 박에 없음. Collision을 많이/적게 일어나게 하느냐의 차이

Weak collision resistance //주어진 x에서 y찾기

given x and h(x), infeasible to find y with y ¹ x such that h(y) = h(x)

Strong collision resistance //아무 x에서 y찾기

infeasible to find any x and y, with x ¹ y such that h(x) = h(y)

Desired property: avalanche effect: Change to 1 bit of input should affect a lot of output bits //잘 만들어진 hash는 입력 값이 조금만 바뀌어도 output이 많이 바뀌는 avalanche effect도 있어야 함.  

Efficiency: No efficiency, no meaning for signing appl // hash를 계산하는데 성능/efficiency가 좋아야 함.

Collision이 생길 수 밖에 없는 이유?

Input x 가 hash를 통해 y를 만남. Y는 정해져 있음. input으로 들어올 수 있는 것은 많음. 많기 때문에 동일한 hash값이 나올 수 밖에 없음 Hast의 결과의 크기는 정해져있음.

hash함수에서 collision을 줄이려면?

length를 키워야 함. 얼마나 키워야 할까?를 결정하는 수학적 근거가 되는 것이 => “birthday paradox”임. 결국, collision이라고 하는 수학적 관점에서 강도를 따진다.

 

5.    인증- 3가지 password,smart card, biometric 괄호넣기, ox

6.    3가지 옵션 괄호넣기, ox->마지막 녹음 듣기

//5&6번은 ppt보기