비대화형 ZKP: 지식 증명할 때 상호작용 없음 (증거(x1, x2)를 딱 한번만 전송)과정메세지가 m^e = c (mod N)로 암호화 됨. (e, c, N은 공개됨) 이때 m을 공개하지 않고 m을 알고 있다는 걸 증명이후 검증자가 계산할 때 x1*x2 = c (mod N) 라면 검증 성공(공개/전송된 파라미터에서 에서 m을 알아내긴 어려워 증명자는 m을 밝히지 않고 m을 알고있다 증명 가능!)임의의 정수 r1을 선택(공개x), 이후r2 = m * r1^(-1) (mod N)x1 = r1^e (mod N)x2 = r2^e (mod N)에서 계산된 (x1, x2)를 전송이후 검증자가 계산할 때 x1\*x2 = c (mod N) 라면 검증 성공(공개/전송된 파라미터에서 에서 m을 알아내긴 어려워 증명자는 ..

영지식 증명: 상대에게 구체적인 내용은 알리지 않은 채 어떤 주장을 참이라는 걸 증명하는 방법완전성: 주장이 참이라면 항상 증명을 받아들일 수 있다건실성: 주장이 거짓이라면 증명자가 검증자를 속일 확률이 매우 낮다영지식성: 검증자는 주장이 참이라는 사실만 알 수 있지 그 외의 정보는 모른다대화형 ZKP: 지식을 증명할 때 상호작용 있음 (증거를 여러번 전송)과정p는 매우 큰 소수, g는 Zp의 생성자B = g^a (mod p)로공개 피라미터 (p, g, B)를 합의한다증명자는 w = (k - a*r) (mod p-1)을 통해 w를 계산하고 전달한다.만약 V = g^w * B^r (mod p)가 만족한다면 검증 성공이 과정을 여러번 반복해 증명자가 a를 알고 있을 확률을 높인다.증명자는 임의의 정수 k (..

ElGamal 서명: D-H 알고리즘의 발전형디피-헬만 알고리즘에서 사용했던 (g, p, y)를 사용하면서 서명기능까지 있다!과정큰 소수 p와, g, 비밀키 x선택 (단, 1y = g^x (mod p) 계산공개키: (p, g, y), 개인키: x이후 서명 검증y^r*r^s (mod p)= g^M' (mod p)라면 유효함서명(r, s)해싱: M -> M'랜덤값 k를 선택 (단 1 r = g^k (mod p)s = k^(-1)(M' - xr) (mod p-1) (단, k^(-1)은 mod p-1에서 곱셈 역원)예앨리스가 밥에게 서명과 메세지를 보낸다고 한다. 파라미터는 g = 7, p = 11을 합의해놨다. (편의를 위해 작은 소수로 정함.)앨리스의 개인키 = 3, 밥의 개인키 = 4앨리스의 공개키 = 7..

디지털 서명: 메세지는 서로만, 그러나 증명은 아무나 할 수 있게역할송신자의 신원 증명메세지가 중간에 조작되지 않았단 증명메세지를 자신이 보냈다는 걸 부인하지 않게 하는 증명RSA 서명이전에 RSA를 사용할 땐 앨리스만 개인키를 정했으나, 디지털 서명에서는 송신자인 밥도 소수 2개를 고르고 공개키, 개인키를 생성한다.이후 밥은 보낼 메세지를 해시로 바꾸고 공개한다.공개된 메세지 해시에 개인키로 서명을 한다.밥의 공개키로 서명을 복호화하고, 만약 이것이 메세지 해시와 같다면 이 메세지는 밥이 보낸거라 할 수 있다.예)암호학 둘러보기 9 참고공개 파라미터(7), 보내는 메세지(8) 등 이전 RSA와 동등한 조건이라 가정할 떄,이전과 같이 밥은 앨리스의 공개키(N)으로 암호화: C = 8^7 (mod 15) ..

RSA: 비대칭키 암호화 방식디피-헬만과는 다르게 서명까지 지원해 안전함. (상대방의 공개키를 이용해 암호화하기 때문)과정메세지 보내는 A, 메세지 받는 B이고 공개된 파라미터 e가 있다.B의 공개키(N): N = p*q (p, q는 매우 큰 소수)B의 개인키([d]): [d]*e = 1 (mod[p-1]*[q-1]) (모듈러 역원 구하기. 만족하는 정수 d는 1개밖에 없으니 안심)A가 보낼 메세지 암호화(C): C = M^e (mod N)B는 자신의 개인키로 복호화(M): M = C^[d] (mod N)예)밥이 앨리스에게 8이란 메세지를 보낼 때, e = 7이라는 파라미터로 합의했다.앨리스는 비밀스럽게 p = 3, q = 5라 정했다. (원래 p, q는 큰 소수이지만 예시라 간단한 수 사용함.)공개키:..

비대칭키 암호: 서로 다른 키를 이용해 메세지를 암호화, 복호화하는 암호    서로 같은 키를 사용해 암호화하는 대칭키 암호에서 키가 중간에 탈취되어 암호가 뚫리는 문제를 해결함. (직접 키 교환이 아니라 각자 가지고 있는 키로 암호/복호화) 모듈러 연산: 나머지 연산 %    예) 4 (mod 3) = 1이산 로그: 이산 거듭제곱 계산은 쉽지만 역방향인 이산 로그는 어렵다는 것을 이용    모듈러 연산에 닫혀있는 Zp에 대해 g^x (mod p) = y 는 쉽지만 g, p, y를 가지고 x를 계산하긴 어렵다.    특히 p가 커질수록 순환군의 크기도 커지므로 계산이 더 어려워진다.    예) g = 2, x = 3, p = 7        y = 2^3 (mod 7) = 8 (mod 7) = 1    ..

Rijndael: AES의 기원 알고리즘    Rijndael은 블록 크기가 128, 192, 256비트인 경우에서 작동하고 AES는 블록 크기가 128비트로 표준화된 것이다. AES: DES보다 더 보안성 있는 블록 암호    DES보다 더 큰 블록크기, 키 길이, 암호 라운드 수    DES는 페이스텔 구조를 사용한다면, AES는 SPN구조를 사용한다.    이 때문에 DES보다 AES가 더 보안성이 높다. AES의 구성 요소AddRoundKey: 라운드키와 메세지 XORSubBytes: S-box를 사용해 변환ShiftRows: 비트 섞기 (각 행을 시프트)MixColumns: 열 단위로 섞기AES의 구조첫번째 라운드AddRoundKeySubBytesShiftRowsMixColumnsAddRound..

simple DES 직접 구현해보기 간단하게 단일 메세지 블록(12비트)에 대해 구현해보겠다. 조건들은 다음과 같다.    메세지: 111111101010    마스터키: 001100111    함수 f: 1바퀴 왼쪽 회전 시프트, 이후 마지막 비트 2개 추가    S1, S2: 각각 2x8행렬, 각 행은 할때마다 랜덤으로 0~7의 중복 없는 행 생성됨. 기타 코드 설명    파이썬에서 그냥 시프트를 하면 앞에 있는 0은 무시됨(0001 -> 1) 따라서 문자열로 바꿨다가(bin, zfill) 다시 수로 연산했다가(int(x, 2)) 함. 코드#simple DES#회전 시프트용 함수: x를, k만큼 시프트, x길이def l_rot(x, k, n): return bin(((x > (n - k)))[2..

DES: 라운드가 16개고, 64비트 블록 단위, 마스터키도 64비트의 알고리즘키 생성 알고리즘회전 시프트: 틈만 나면 회전 시프트를 한다...패리티 드롭:실제로는 패리티 비트 등의 검수용 비트가 들어있어 64비트가 아닌 56비트에 대해 암호화를 수행한다. 따라서 마스터키도 일부 8비트를 무시해 56비트가 된다압축: 비트 수를 줄이는 방법. 일부 비트값이 빠져있는 테이블을 통해 줄인다. (여기서는 56비트를 더 줄여 48비트로 만드는데 사용)암호화각 라운드마다L(i) = R(i-1)R(i) = (L(i-1)) XOR f(R(i-1), K(i))를 반복한다.복호화단순히 암호화의 역 과정이다.DES에 대한 공격브루트 포스: 가능한 모든 키에 대해 무차별적으로 대입하기    마스터키가 56비트이므로 2^56 ..

DES: 블록 암호 알고리즘 (평문을 블록단위로 쪼갠 후 암호화)    S-box로 난수화: DES의 핵심, 입력에 따라 암호문 생성.     (각 행은 0~행 길이-1의 무작위 수이며 같은 행엔 같은 숫자가 반복되지 않는다.)    파이스텔 암호를 이용한다 (아래 simple DES 과정 참고) simple DES: DES의 간단한 버전 (simple DES에서는 메세지 12비트, 키 9비트로 구현한다.)S-box:S0(4x16행렬): 입력(6비트) -> S-box -> 출력(4비트)S1, 2(각각 1x8행렬): 입력(4비트) -> S-box -> 출력(3비트)파이스텔 암호과정평문 M을 각각 (Li, Ri) 두 부분으로 쪼갠다.함수 f를 통해 Ri의 비트를 확장한다.키 Ki는 마스터 키에서 i-1번째 ..