Sign in Subscribe

블록체인 2 - cryptography for blockchains

Published: / Updated:

Cryptography란 무엇인가?

  • cryptography : 암호기술 - 비밀 시스템 설계
  • cryptoanalysis : 암호 분석 - 비밀 시스템 해독 및 공격
  • cryptology : 암호학 - 위 두가지 모두를 포괄하는 비밀 통신에 관한 과학
  • crypto : 문맥에 따라 위의 모든 것을 지칭 가능함.

crypto, 즉 암호학의 목표 4가지는 다음과 같다.

  • 기밀성
    • 대칭키 암호(블록 사이퍼, 스트림 사이퍼)
    • 공개키 암호
  • 데이터 무결성
    • 임의 길이 해시 함수
    • 메세지 인증코드(MACs)
    • 전자서명
  • 인증
    • 개체인증
    • 데이터 출처인증
      • MACs, 전자서명
  • 부인방지(전자서명)

기본 정의

  • cipher (암호시스템) : 평문을 암호화(encrypt)하는데 사용됨
  • ciphertext (암호문) : 암호화의 결과물
  • decrypt (복호화) : 암호문에서 평문을 복구하는 과정
  • key (키) : 암호 시스템을 설정 하는데 사용됨
  • symmetric key (대칭 키) : 암호화와 복호화에 동일한 키 사용
  • public key (공개키/비대칭키) : 암호화(또는 검증)에는 공개키, 복호화(또는 서명)에는 개인키 사용

암호학의 기본 가정은, 암호 시스템 즉 알고리즘이 공격자에게 완전히 알려져있다고 가정하고 오직 KEY 만이 비밀로 유지된다.

대칭키는 동일한 키로 palintext 를 encypt를 통해 ciphertext 로 만들고, 또 decrypt해서 다시 plaintext 로 만들 수 있다.

암호의 종류

  • Random functions (무작위함수) : 해시함수 - 임의 길이의 입력을 받아 고정길이의 출력을 생성함
  • Random generators (무작위 생성기) : 스트림 암호 - 짧은 입력을 받아 긴 출력을 생성한다
  • Random permutations (무작위 순열) : 블록암호 - 키를 기반으로 고정 크기 입력을 고정 크기 출력으로, 또 반대로 변환하는 역함수가 있는 함수
  • Public key encryption (공개 키 암호) : 누구나 암호화할 수 있지만, 오직 키 소유자만 복호화할 수 있다.
  • Digital signatures (전자 서명) : 오직 키 소유자만 서명할 수 있지만, 누구나 검증할 수 있다.

해시함수에 들어가면, 임의 길이의 메세지가 고정길이의 해시값으로 변환된다.

이렇게, 해시테이블이라는 자료구조를 보면,

keys 를, 해시함수가 buckets 의 고유번호로 변환해준다.

john smith 와 sandra dee를 보면, 같은 152번 버킷으로 변환되었지만, 오버플로 영역에 추가로 저장되어 충돌해결이 된다.

암호학적 해시함수의 특징 : SHA256

  • 역상저항성(primage resistance) : 해시값을 보고, 원래의 입력값을 찾는 게 매우 어렵다.
  • 제2 역상저항성 (2nd primage resistance) : 특정 입력값과 그 해시값을 가지고, 동일한 해시값을 갖는 다른 입력값을 찾는게 매우 어렵다.
  • 충돌저항성 (collision resistance) : 해시 값이 같아지는 서로다른 두 입력값을 찾는게 매우 어렵다

암호학적 해시함수 h(x)는 다음을 제공해야한다

  • 압축 : 출력 길이가 작아야한다
  • 효율성 : 어떤 x에 대해서도 h(x)를 계산하기 쉬워야한다.
  • 일방향성 (역상 저항성) : 의 다른 의미로, 출력값으로 입력값을 유추할 수 없어야한다.
  • 약한 충돌저항성 (제2 역상 저항성) : x와 h(x)가 주어졌을 때, h(x)와 같은 h(y)를 가지는 y를 찾을 수 없어야한다.
  • 강한 충돌저항성 (충돌 저항성) : h(x) = h(y) 를 만족하는 x =/=y인 x와 y를 찾을 수 없어야한다.
  • 수학적으로 많은 충돌들이 존재하지만, 특정해서 찾을 수 없어야한다는 의미다.

생일 역설

방에 N명의 사람이 있을 때, 그중 누군가가 나와 생일이 같을 확률이 1/2 이상 되려면 N이 얼마 이상이어야하나?

1/2 = 1-(364/365)^N

이걸 풀면, n=23이다.

즉, 방에 23명의 임의의 사람이 있으면, 그 중 어떤 두 사람이 생일이 같을 확률이 0.507이다. 즉 50프로 이상이다.

해시함수의 출력길이가 N비트면, 2의 n승 개의 해시 값이 존재한다.즉, 2의 n승 대칭키, 즉 n비트 대칭키는 2의 n-1승번의 작업으로, 함수 충돌을 나타낼 수 있다.

유명한 암호학 해시함수들

  • MD5 : 리베스트가 발명, 128비트 출력. 쉽게 충돌 찾기 가능
  • SHA-1 : 미국정부 표준으로, 2017년에 깨짐
  • SHA-2 : SHA-1이랑 비슷해서 좀 불안함
  • SHA-3 : 2015년에 NIST가 keccak을 표준으로 채택함. 전과는 알고리즘이 다름

우리가 흔히 가입하는 홈페이지들도, 비밀번호의 원문을 저장하지않고, 해시함수에 넣어서, 생성된 해시키를 회사 DB에 저장하고, 또 로그인할 때 비교한다.

Random bit 난수 생성

암호학적 프로토콜은, 키와 nonce 생성을 위해 예측 불가능한 난수 비트가 필요한데, 난수 소스로 주변기기 하드웨어 응답 시간이나 아날로그/디지털 변환기 노이즈 (사운드카드, 카메라), 네트워크 패킷 타이밍 및 내용이나 고해상도 시간을 활용하는데,이런 소스들은 단독으로 완벽하지 않으며, 이들을 해시함수에 입력해서 엔트로피를 응축 시켜서 난수 비트를 만든다.

nonce(number used once) : 특정 목적을 위해 한번만 사용되고 폐기되는 임시 값으로, 주로 난수 또는 의사 난수로 생성된다.

블록암호 (blockciphers)

블록 암호는 키에 의존하는 순열 함수로, 고정된 크기의 비트 블록 단위로 작동한다. 64비트나 128비트 처럼.

Confusion : 키와 암호문 사이의 관계를 최대한 복잡하게 만든다

Diffusion : 평문과 암호문 사이의 통계적 관계를 제거한다.

AES( advanced encryption standard)

기존 DES(data encryption standard)를 대체함.

90년대 후반 NSA(미국 국가안보국)이 공개적으로 참여한 경쟁을 통해 선정됐다.

최종적으로 레인달 알고리즘이 선택되었고 반복구조의 블록암호이다.

비대칭 암호 기본 요소

  • 소인수분해 기반 암호
    • RSA (2020년에 829비트 숫자 소인수분해 성공)
  • 이산로그 기반 암호
    • Diffie-Hellman 키교환
    • ElGamal 전자서명
  • 타원곡선암호(Elliptic Curve Cryptography, ECC)

PKI(Public key intrastructure)

인터넷 상에서 A가 자신을 A라고 주장할 때, 우리는 그걸 어떻게 믿을 수 있을까? 정부같은 신뢰기관이 보증 '여권' 같은걸 발급해주면된다.

pki는 이처럼 '신뢰할 수 있는 기관' 이 특정 '공개키'가 특정인의 것임을 보증해주는 시스템 전체를 일컫는다.

  • CA(Certification Authority, 인증기관)
  • 공개키 인증서 (CA가 발급함)
    • A(주체) : 인증서의 주인
    • K : 그 주인의 실제 공개키
    • T,L (유효기간) : 이 인증서가 유효한 시간 (시작시간과 기간)
    • CA의 디지털 서명 (CA가 개인키로 서명함)

서명에 대한 설명

  • 기밀성(내용 숨기기)
  • 무결성/인증 (변조, 사칭 방지)

이 두개는 다르게 이뤄진다.

  • 기밀성을 위해서, A가 B에게 '특정 평문 메세지'를 보낼 때 A는 모두가 알고 있는 B의 공개키를 이용해서 메세지를 암호화해서 B에게 보내. 그러면 B는 자신만 알고있는 B의 개인키를 이용해서 그걸 복호화해서 내용을 확인해.
  • 이 과정에서 변조, 사칭이 되지 않았음을 확인하기 위해서, A는 '특정 평문 메세지'를 해시함수로 해시한 값을 자신의 개인키를 이용해서 암호화한다. 이게 서명이다. B에게 서명과 B의 공개키로 암호화한 내용을 같이 보낸다.
  • 그러면 B는 자신의 개인키로 내용을 확인해보고, 무결성 확인을 위해서, 서명을 A의 공개키로 복호화한다. 복호화하면 해시값이 나올텐데, 받은 평문을 A가 사용한 해시함수로 해시해서, 그 값과 서명을 복호화해서 나온 해시값이 일치하는지 확인한다.
  • 근데 이때, 내가 사용하는 A의 공개키가 진짜 A의 것이 맞는지 의심되기 때문에, 즉 공개키 전달과정에서 신호 탈취가 일어날 가능성을 염려해서, A는 B에게 이 전달 활동 전에, '공개키 인증서' 를 준다. 이것은 'A의 공개키 + CA의 서명'으로 이루어져있다.