너와 나의 스토리

왜 Block Cipher에 대해 Finite Field를 이용하는가? AES를 구성하는 함수들 Substitution Transposition (permutation) Multiple rounds Simple bit operations (XOR 같은 ) Bit randomizion effect input에 대해 output이 랜덤하게 나오는 것 같은 느낌을 줌 Field multiplication이나 Field inversion이 이런 randomizion effect 역할을 함 덧셈은 그다니 randomizion 효과가 없음 덧셈 반복해도 효과 x 곱셈이나 역연산은 복잡도를 증가시킬 수 있음 Binary Field의 근거 우리는 편의성과 구현 효율성을 위해 낭비되는 비트 패턴이 없는, 주어진 수의 비..

필요한 사전 지식: 2020/10/23 - [Computer Security] - [컴퓨터 보안] Classical Encryption Techniques Symmetric encryption(대칭 암호) 현대 대칭 암호를 분류할 때, Stream ciphers와 Block ciphers 두 종류로 분류한다. Stream cipher 가장 완벽한 암호: bit 단위로 plain text를 쪼개서, 그 plain text와 같은 길이의 랜덤 bit sequence를 key로 만들어, XOR 해 암호화하는 One-time pad 방식 예: Vernam 현실적으로는 이 방식을 안 씀. 왜냐하면, 그 plain text와 같은 길이의 key sequence를 안전하게 송수신자 사이에 공유해야 하는데, 이 정도의..

Definitions Plaintext 암호화하려는 대상(숨기려는 대상) Ciphertext (암호문) 암호화가 된 결과물 그냥 봐서는 내용을 알아볼 수 없다 Enciphering/encryption (암호화) plaintext를 ciphertext로 변환하는 과정 Deciphering/decryption (복호화) ciphertext로부터 plaintext를 복구하는 것 Cryptography 암호화 기술을 연구하는 학문 Cryptographic system/cipher 암호화하는 알고리즘, 논리 Cryptanalysis 암호화된 것들을 공격하는 것 enciphering 지식이 없이 메시지를 deciphering하는 데 사용되는 기술 예: Ciphertext로부터 plaintext를 얻거나, 암호화할 ..

Groups(G) : 집합과 연산(·) 한 가지를 합쳐서 정의 연산(·)이 덧셈인 경우 additive group이라고 부른다. 곱셈인 경우 multiplicative group. Group은 하단의 A1~A4의 성질을 만족한다.. (A1) Closure a와 b가 G에 속하면, a·b는 G에 속한다. 집합의 원소와 관계가 있는 원소가 항상 그 집합에 속한다는 성질 (A2) Associative(결합 법칙)이 성립 a·(b·c)=(a·b)·c for all a, b, c in G (A3) Identity element(항등원)이 존재 a가 G에 속할 때, a·e = e·a = a라면 e는 G에 속한다. 항등원 e를 가지는 것 (A4) Inverse element(역원)이 존재 각 a가 G에 속할 때, a..

* 해당 글의 최하단에 Miller-Robin test 설명이 요약되어있습니다. Prime Number(소수) : 1과 자기 자신으로만 나눠지는 수 number theory에서 중요한 역할 1보다 큰 모든 정수는 소수의 거듭제곱의 곱으로 유일하게 표현 가능하다. Fermat's Theorem(페르마 정리) [p: 소수, a: p로 나눠지지 않는 양의 정수]라면 $a^{p-1}$ ≡ 1 (mod p) [p: 소수, a: 양의 정수]라면 $a^{p}$ ≡ a (mod p) 위 식은 a가 p로 나눠지는지더라도 성립 Euler's Theorem(오일러 정리) Euler totien function ϕ(n) ϕ(n): 1부터 n까지의 양의 정수 중에 n과 서로소인 것의 개수 n이 두 소수의 곱이라면 -> n = ..

2020/10/22 - [Computer Security] - [컴퓨터 보안] 정수론 기초 - Divisibiliy, GCD, Congruences, Modular, 역원 Euclidean Algorithm(유클리드 호제법) 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나. a%b == r (a를 b로 나눈 나머지 r) a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, gcd(a, b) = gcd(b, r) = ... 를 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 코드: int gcd(int a, int b) { if (b == 0) return a; gcd(b, a%b); } Extended Euclidean Algorithm GCD(1759, 5..

Divisibility a|b a는 b의 약수 b÷a의 나머지는 0 ex) 13|182 특징 a|1이면 -> a=±1 a|b이고 b|a이면 -> a=±b b!=0인 모든 b는 0을 나눔 a|b이고 b|c이면 -> a|c b|g이고 b|h이면 -> b|(mg+nh) GCD(Greatest Common Divisor) a, b의 최대 공약수 gcd(a, b)로 표현 [gcd(0, 0) = 0]으로 정의 gcd(a, b) =c c는 양의 정수 c는 a와 b의 약수 a와 b의 모든 약수는 c의 약수 Congruences (a mod n) = (b mod n)인 경우 두 정수 a, b를 "congruent modulo n"이라고 한다. 표현: a ≡ b (mod n) a ≡ 0 (mod n)이면 n|a이다. 특징..

문제: www.acmicpc.net/problem/16954 8×8인 체스판에서 탈출하는 게임 체스판의 모든 칸은 빈칸(.) 또는 벽(#) 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다. 이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다. 1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없..