AYSTORY

Public Key Cryptography소인수 분해 문제 (Prime Factorization)→RSAn=p×q일 때, p,q를 알아내는 것은 쉽지 않음 (NP-난해).이산로그 문제 (Discrete Logarithm)→ElGamal주어진 g,y,p에 대해 g^x ≡ y (mod p)를 만족하는 x를 구하는 것 역시 매우 어려움.이 두 문제의 난이도를 이용해 RSA, ElGamal 같은 공개키 암호가 동작한다.Key Exchange or Establishment시나리오Alice와 Bob은 카페의 공용 인터넷을 통해 민감한 데이터를 주고받고 싶어하지만, 잠재적인 도청자로부터 통신을 보호해야 합니다. (암호화가 필요합니다!)그러므로, 그들은 민감한 데이터를 암호화할 key가 필요.안전하지 않은 채널을 통해..

1. ⟨a⟩ 정의⟨a⟩={ak∣k≥1인 정수}ak는 a⊕a⊕⋅⋅⋅⊕a를 k번 반복한 것2. subgroup 성질닫힘성(closed under ⊕):임의의 두 원소 ai,aj∈⟨a⟩에 대하여 ai⊕aj=a i+j 역시〈a〉에 속하므로 closed.항등원(identity):군 G의 항등원 e는 e=a^k 형태로 나타나진 않더라도, 〈a〉에는 “k=0”를 허용해서 a^0=e를 포함시키기도 하고, 아니면 “k≥1” 사이클을 돌면서 결국 항등원에 도달합니다.역원(inverse):a의 역원 a^(-1) 역시 어떤 거듭제곱 a^m로 나타낼 수 있으므로 〈a〉에 들어 있습니다.3. 생성원 (generator)만약 이 부분군 〈a〉가 원래 군 G 전체와 같다면—즉 ⟨a⟩=G,—그때 우리는 “a가 G를 생성한다”라고 하고..

Number theory and cryptographic algorithms (Part 3)Spring 2025 Computer AlgorithmsNumber theory basicsZn∗의 원소 개수를 오일러 파이 함수 ϕ(n) "Euler phi function"이라고 부름.여기서 p는 n을 나누는 모든 소수.만약 p가 소수라면, ϕ(p) = p−1.먼저 n=9일 때, 9를 소인수분해하면, 9 = 3^2.따라서 “n을 나누는 소수들”은 단 하나, p=3밖에 없다.Cryptographic Algorithms and Protocols수론은 현대 암호 알고리즘·프로토콜의 핵심 도구.많은 보안 기법이 수론 기반으로 설계됨.이번 강의에서는 다음 두 개의 공개키 암호화 예시를 다룸:Merkle–Hellman K..

Number theory basicsIf G=(S,⊕) is a group, S'⊂S, and G' = (S,⊕) is also group, G' is subgroup of GAlso, if S'≠S, G' is a proper subgroup of GExamplesZ: integers, E: even integers, (E,+) is subgroup of (Z,+)For G=(S,⊕), we have an inverse element a' for a∈S and define a^k and a^(-k) (for non-negative integer k)a^0=ea^k=a⊕a⊕...⊕a(k a's)Also, we have G=(S,⊕) and subgroup S'⊆S. Then, if a⊕b∈S' for a..

Number theory and cryptographic algorithms Introduction to number theory and cryptographic algo.수론은 이러한 작업을 수행하는 데 있어 가장 유용한 주요 도구입니다. 많은 현대 암호 기법이 수론에 기반해 설계되어 있습니다.위와 같은 서비스의 보안은 종종 (NP 클래스에 속하는) 풀기 어려운 문제들의 난이도에 의존합니다. 예를 들어, 큰 합성수의 인수분해 문제나 이산 로그 문제 등이 있습니다.“수론과 암호 알고리즘”은 알고리즘 설계 및 분석의 틀 안에서 수론과 암호학의 계산적 측면을 연구하는 학문 분야입니다.Number theory basics임의의 집합 S와 이항 연산 ⊕에 대해, (S,⊕)가 군이 되려면 다음 네 조건을 만족해..

TopicsRadix sortSearchingfindMinMaxfind2ndMaxgeneral selection (kth smallest)median-of-medians rule Lower bound proof (in the worst-case) for sorting by comparisons비교 기반 정렬의 최악 하한 증명can be represented as a decision tree 결정 트리(Decision Tree) 모델예를 들어, 세 개의 키 a,b,c를 정렬하는 다음과 같은 알고리즘을 생각해 보자.리프 노드(leaf nodes) 는 가능한 해답(정렬된 순서)을 나타내며, 총 n! 개가 있음.n개의 키로 만들 수 있는 모든 순열 수와 일치.※ 모든 키 x1,x2,…,xn는 서로 다르다고 가정..