🔐 암호학(Cryptography)의 원리 - 알고리즘, 디지털 서명, 양자 암호

본 포스팅은 학교 수업에서 진행하는 이론,실습에 대해 정리하는 포스팅 입니다. 공부용으로 작성하는 포스팅으로 오류가 있을 수 있습니다.

 

암호학은 디지털 세상에서 정보를 안전하게 보호하는 핵심 기술이다.

이 포스팅에서는 암호학의 기본 개념, 대칭 및 비대칭 암호화, DES, RSA 알고리즘, 메시지 다이제스트, 디지털 서명의 수학적 원리, 양자 암호 까지 가볍게 정리하였다. 

암호를 분석하는 내용을 주로 다루는데, 암호를 분석하는 것은 그 자체로 암호화된 데이터에 대한 공격으로 간주할 수 있다.

 

암호 분석

암호분석 방법 

• 단일 메시지 해독
  특정 암호화된 메시지를 해독하려고 시도.
• 암호화 메시지에서 패턴 찾기
  암호화된 메시지에서 반복되는 패턴이나 규칙성을 찾는 방법.
• 의미 추론
  암호를 직접 해독하지 않아도 메시지 길이 또는 빈도를 통해 일부 의미를 유추.
• 키 추론
  하나의 메시지를 해독한 뒤 이를 기반으로 다른 메시지의 키를 추론.(one bit -> all break)
• 구현 및 환경 취약점 발견
  암호문 자체로는 완벽하나, 암호화 알고리즘의 구현 혹은 환경에서의 약점을 파악.
• 암호화 알고리즘의 일반적인 취약점 발견
  특정 구현과 관계없이 알고리즘 자체의 설계 결함을 찾아내는 방법.

 

암호분석의 입력값(Inputs)

암호 분석가는 다음과 같은 데이터를 기반으로 분석을 진행한다:

• 암호문 만으로 분석(Ciphertext Only)
  암호문만으로 패턴, 유사점, 불연속성을 찾아내어 분석.
  예) 동일한 암호화 방식을 사용한 다수의 메시지 비교.
• 평문과 암호문 함께 사용(Plaintext and Ciphertext)
  평문과 암호문을 함께 활용하여 변환 과정을 파악. -> public key 사용
  암호문만 사용하는 것 보다 정보가 더 많다 -> 공격자가 할 수 있는 일이 많아짐 
  • 알려진 평문(Known Plaintext): 일부 알려진 평문과 해당 암호문이 있을 때 사용.
  • 분석가가 선텍한 평문(Chosen Plaintext): 분석가가 평문을 선택하고 암호화 과정을 거쳐 암호문을 생성하여 분석.

암호학의 기본 요소

1. 대체(Substitution) : 비트 집합의 일부를 다른 것으로 교환(bit단위로)하는 방식으로, 원본 메시지의 구성 요소를 대체하여 보호한다.

• ex) Caesar Cipher(규칙에 따라알파벳 변경): BANANA에서 A를 Z, B를 C, N을 K Z를 X로, 한비트씩 앞당겨서 CZKZKZ로 변환

2. 전치(Transposition): 평문의 문자나 비트의 순서를 재배열하여 패턴을 갖추는 방식으로, 평문 구조는 유지되지만 위치가 변경되어 분석이 어렵다.

• ex) 행렬 형태로 데이터를 재배열하거나 문자의 순서를 섞는다 (BANANA -> AABNAN)

3. 혼동(Confusuion) : 평문, 키, 암호문 간의 관계를 복잡하게 하여 보안성 강화

4. 확산(Diffusion): 평문 전체의 정보를 암호문 전반에 걸쳐 분산시켜 보안성 강화, 암호문 일부가 바뀌면 전체가 크게 바뀌도록

 

이 4가지 요소는 암호학에서 알고리즘을 설계하는데 필수적으로 사용된다.

 

One Time Pads(OTP)  - perfect security

암호화의 완전한 보안을 제공하는 방법 중 하나로 알려져있다. 이론상으로는 어떤 방법으로도 깰 수 없는, 안전한 방법이다.

암호화는 XOR를 통해 이루어진다.

 

현실적으로는, 평문과 길이가 똑같은 key를 안전하게 공유하는게 전제가 되어야 하므로 실질적으로 사용하기 어렵다. 

만약 이렇게 안전하게 공유가 가능하다면, 그 방법으로 key가 아닌 메세지를 공유하면 되기 때문에 모순

 

좋은 암호화의 특징 of Shannon

Claude Shannon은 좋은 암호문의 조건으로서 다섯가지 주요 특성을 제시하였다.

 

1. 측정가능한 안전성 : 보안의 수준은 컴퓨터의 속도나 리소스 등 여러 요소를 고려해야한다. 예를들어 컴퓨터로 몇번의 연산을 거쳐야 하는지, 길이는 어느정도로 할 것인지(현대에는 2^128 비트는 되어야 안전한편)

2. 간단한 키와 알고리즘 : 공격을 하기엔 어려워야 하지만, 키를 생성, 암호화, 복호화하는 사람 입장에선 간단해야 한다. 또한 같은 알고리즘을 구현한다면 최대한 빠르게 만들어야 간단하고 취약점도 적다

3. 오류 전파 방지 : 암호화 과정에서 발생한 일부 에러가 전체 메시지에 영향을 미쳐선 안된다.

3. 효율성: 암호화된 텍스트는 원문보다 작아야하며 , 작으면 작을 수록 좋다. (대칭키에서는 만족하지만, 공개키를 쓰면 어렵다)

 

이 외에도 완벽한 암호체계는 신뢰할 수 있는 수학적 기반 위에서 설계되어야 하고, 전문가에 의해 안정성이 검증되어야 하며, 오랜 시간동안 검증되어 안전함을 평가받아야한다.

 

 

대칭 암호화

DES 알고리즘 원리

블록 암호화

현실적으로 One Time Pad는 구현할 수 없으니, 블록 암호화를 사용한다. 블록 암호화는 평문 블록 전체를 가지고 같은 크기의 암호문 블록을 생성하는 방식이다. 전형적으로 64비트를 사용하며, stream보다 더 넓은 범위에 사용된다.

대부분의 네트워크는 이 블록 암호방식을 따른다.

 

대표적으로 DES 알고리즘이 있다. 

DES자체는 이미 깨진 알고리즘이지만, 이 구조는 다른 대칭키 암호에서도 쓰인다. 

동일한 알고리즘을 라운드 수만큼 반복하여 암호화를 하고, 복호화도 동일한 방식으로 역순으로 진행된다.

1. DES 또한 64비트를 반반씩 Left , Right로 나눠준다. 

2. Key로는 56비트의 키를 사용한다. (8비트는 parity check 에 사용)

3. Right 데이터를 확장시켜 48비트를 만들고, Round Key는 순열로 치환시켜서(Permutation) 48비트를 만든다.

4. 48비트로 맞춘 두 데이터를 XOR연산으로 결합, XOR로 암호화를 하면, 동일한 알고리즘으로 복호화도 가능하며, key값이 다르면 같은 내용을 암호화해도 다른 결과를 만들어낸다.

5. 결합된 암호키 f(R, Key)는 S-box에서 대체(Substitution) 후 일부 비트가 선정(choice)되어 32비트가 된다.

6. 다시 Permutation을 하고 Left의 데이터와 XOR을 한다.

7. L데이터와 XOR을 한 결과는 새로운 Right 데이터가 된다. 새로운 Left 데이터는 1번에서 나눴던 Right비트를 그대로 복제해서 가져온다. -> 즉 새로운 Left 데이터는 이전 라운드의 Right데이터와 같다.

8. 이 과정을 라운드 수만큼 반복한다.

9. 최종 라운드 후 좌우 데이터를 다시 결합하고 최종 순열로 암호문을 생성한다.

 

DES의 복호화

XOR로 암호화를 했기 때문에, 동일한 알고리즘으로 복호화가 가능하다. 

수식으로 DES내용을 정리해보자,
(1)을 보면, 구버전 j-1의 R를 그대로 새로운 L로 사용하고, 새로운 R은 구버전 R로 키를 만들어 구버전 L과 XOR연산을 한다.

 

복호화는 이걸 반대로 하면 된다.

최근 라운드인 Lj로 이전 라운드의 Rj-1을 구하고, 최근 라운드의 R과, 이전라운드의 Key(이번 라운드의 L로 만든 Key와 동일)와 XOR연산을 해주면 이전 라운드의 Lj-1 데이터도 구할 수 있다. 암호화 한 라운드 수 만큼 이 과정을 반복하면 된다.

 

DES는 56비트 키를 사용하기 때문에 무작위 공격(Brute Force)에 취약하다.

이를 보완하기 위해 AES, 3DES등 사용

 

체이닝(Chaining)

블록 암호화에서 Chaining은 데이터 보안을 강화하기 위해 블록의 의존성을 추가하여 각 블록의 암호화를 이전 블록과 연결하는 방식이다.

DES에서, 이전 라운드의 블록을 사용하는 것이 체이닝.

같은 키로 똑같은 메시지를 암호화 하면 같은 암호가 나오기 때문에 문제가 될 수 있는데, 이를 체이닝으로 방지할 수 있다. 

ex) RSA_AES_128_CBC

첫 블락인 헤더는 XOR하기엔 이전 블락이 없어서 스킵

예시에서, 이전 블록의 암호문 apqrwx를 사용하여 새로운 암호문을 생성하고, 그 다음 데이터에서 이전 블록과 다른 데이터를 사용하여 암호화한다. 체이닝을 통해 새로운 패턴이 생성된다.

 

Initialization Vectors

IV는 암호화 과정에서 사용되는 무작위 데이터 블록이다. 입력과 키가 동일해도 출력이 다르게 생성되도록 보장한다.

위 예시와 다른 점은 첫번째 헤더에 안쓰는 블락 (IV)를 넣어주는 것이다. 이게 초기설정이고, 이를 적용하면 헤더부터 끝까지 다 값이 달라진다.

 

 

AES(Advanced Encryption) 알고리즘

DES의 단점을 보완한 알고리즘으로 DES처럼 반복적인 라운드를 통해 암호화를 한다.

1. Byte Sub: DES와 같이 Substitution  (Byte 단위로 쪼갠다)

2. Shift Row: 데이터의 행을 좌측으로 이동시켜 혼합성(Confusion)을 증대시킨다.

3. Mix Columns: 행렬 곱셈을 통해 각 열의 데이터를 혼합 (그림 예시는 4x4 행렬곱)

4. Add Round Key: 데이터를 XOR 연산하여 현재 라운드의 키를 추가

 

위 과정을 반복하여 최종적으로 암호화된 내용을 출력한다. 10라운드 반복하며 암호화는 역순으로 진행한다.

 

AES는 1997년 발표된 이후 철저한 검증을 거쳐 현재도 강력한 보안 알고리즘으로 사용중이다. 

즉, 좋은 암호화의 특징인, 오랜 시간에 걸쳐 검증되어야 한다는 조건을 만족한다. 아직까지 취약점을 찾은 공격이 없다.

 

 

비대칭키 암호화

RSA

RSA또한 1978년 도입 후 오랜 시간 암호 분석을 거쳤으며, 현재까지 결함이 발견되지 않은 안정적인 암호화 알고리즘이다.

큰 소수를 소인수분해하는 방식에 기반한다. 이 문제를 가장 빠르게 해결하는 알고리즘도 지수적인 시간이 걸리게 된다.

암호화에는 e, 복호화에는d 키를 사용하며, 이 키들은 서로 교환이 가능하다.

과정

평문 블록 P와 암호문 C는 위와 같은 과정을 통해 암호화, 복호화 된다. 

n은 두 소수의 곱이며, n은 결과의 범위를 제한하며 공개되어있는 값이다. e는 공개키의 지수, d는 비밀키의 지수값이다.

 

수학적인 관계를 살펴보면, 모듈러 산술의 대칭성을 활용하여 암호화와 복호화를 역순으로 동작하도록 하였다.

암호화와 복호화는 상호 교환이 가능하고, 먼저 암호화를 하고 복호화를 하거나, 복호화한 후 암호화해도 동일한 결과를 얻는다.

이처럼 강력한 수학적 기반을 갖추고 있어 높은 수준의 보안을 제공한다.

대칭키를 공개할 필요 없이 공개 키와 비밀 키를 사용하여 데이터 보호가 가능하여 안전한 데이터 교환이 가능해진다. 

 

구성요소

RSA암호화 키는 (e,n) 쌍으로, 복호화 키는 (d,n) 쌍으로 구성된다. n은 두 소수 p,q의 곱으로 매우 큰 값이어야한다.(크기가 커야 추론하기 어렵다)

 

키 생성과정

1. 소수 p와 q 선택 : p,q는 300자리 소수로 선택, n은 600자리(2048비트)크기

2. 공개 지수 e 설정: e는 (p-1)*(q-1)과 서로소인 큰 정수로 선택

3. 비밀 지수 e 계산 : e*d 는 1 (mod(p-1)*(q-1))를 만족하는 d를 계산한다. (d와e는 역수 관계)

 

 

https://kimjoraeng.tistory.com/42

[알고리즘]데이터 암호화 알고리즘 - RSA 암호화

 

 

메시지 다이제스트

데이터 블록의 변화를 감지하기 위한 방법으로, 데이터의 무결성을 보장한다. 

One-way Hash(일방향 해시) 암호화 기법으로서, 공개 키 암호화 및 디지털 서명, 데이터 무결성 검사, 사용자 인증, 통신 프로토콜 등 많은 곳에 사용된다.

 

일반적인 자료구조에서 쓰이는 해시맵과 달리 암호학적 목적으로 사용되는 해시 함수는 아래 조건을 만족해야한다.

현대 해시 함수의 기준

1. 일방향성 : 입력 데이터를 다이제스트로 변환하지만, 다이제스트 값으로부터 원래 입력을 추론이 불가능

2. 충돌회피: 동일한 다이제스트를 생성하는 두 개의 서로 다른 입력값(충돌)을 찾는것이 실질적으로 불가능

 

 

해시 표준 속성

위 표는 주요 해시 알고리즘들의 속성을 보여준다. 현재는 SHA-3-256또는 512가 표준이다. Digest Size 512

 

전자 서명(Digital Signatures)

대표적으로 공인인증서 등에 쓰이는 기술로, 메시지를 만들었다는 것에 대한 신원을 증명하는데 쓰인다.

 

전자 서명은 아래 조건을 필수로 충족해야 한다.

1. (필수)위조 불가성 (Unforgeable) : 비밀 키 없이 서명 생성이 불가능하여 가짜 서명이 불가

2. (필수)진위성(Authentic): 서명자로 부터 온 서명인지 수신자가 확인할 수 있어야 한다.

3. 변조 불가성: 수정 불가

4. 재사용 불가성: 이전 서명 재사용 감지

 

디지털 서명의 생성 및 검증 과정은 다음과 같다.

서명자는 자신의 비밀 키를 사용하여 서명 값을 생성(계산), 검증자는 서명자의 공개키를 사용하여 올바른지 확인

 

이때, 메시지를 바로 해시해서 서명하면, 메시지가 동일하면 해시값도 동이랗게 나온다. 재사용되거나 가짜가 만들어질 수 있으니 메시지에 임의의 난수를 추가하는 Challenge를 생성한다.

공개키 암호와와 비교

공개키암호화는 누구나 public key를 통해 encryption을 할 수 있다. 그리고 이걸 받은 한 사람만 decryption 가능하다.그리고 encryption을 해야 decryption 가능

 

반대로 디지털 서명은 한 사람만 서명(sign, encryption) 가능하고, 아무나 검증 가능(verify, decryption)하다.

 

 

Elliptic Curve Cryptosystems (ECC)

ECC는 타원 곡선을 기반으로 하는 비대칭 암호화 알고리즘으로, RSA 알고리즘의 대안으로 주목받는다.

 

RSA는 강력한 알고리즘이며 널리 사용중이지만, 특허 문제(RSA구현)가 존재하기 때문에 좀 더 Free한 알고리즘으로 ECC가 쓰인다.

RSA보다 암호화에 필요한 키 길이를 짧게 줄이는데 중점을 둔다. 

 

대신 단점으로는 수학적으로 구현하기 어렵다는 점이 있다. 

 

이더리움 비트코인 등에서 쓰인다.

 

 

 

Quantum Cryptography(양자 암호화)

양자 암호화는 물리학에 기반하여 동작하며 수학적 알고리즘 대신 광자의 물리적 특성을 활용한다.

공개키 암호를 대체하는데 쓰이는 기술로, 양자 암호화를 통해 Secure한 채널을 만들 수 있다.

양자 암호화로 비밀키만 교환면 Man in the middle 등의 공격을 방지하는게 가능하다.

 

누군가 이 채널을 관측하는 순간 관측(도청)한 것을 바로 알 수가 있다.(하이젠베르크 불확정성 원리) 관측 당하면 그냥 버리면 된다.

 

아직은 프로토타입 단계로, 실제 사용 가능 수준에 이르기 위해서는 강좌총(Photon GUn)과 수신 장치가 개발 되어야 한다.

10년 내로 가능성이 있지만, 현재는 기술적 어려움과 높은 구현 비용으로 인해 상용화가 어렵다.

 

Post-Quantum Cryptography

Quantum Cryptography와 비슷한 것 같지만 전혀 다른 개념

양자 컴퓨터가 등장한 후에도 안전한 암호 알고리즘을 말한다.

이 기술은 물리가 아닌 수학적 알고리즘에 기반을 두고 있다.