이동식 저장소

Massey-omura 많이 쓰는 암호는 아니지만, 굉장히 특이한 암호 체계이다. 왜냐고? 아무것도 공유를 안 하거든! RSA에서는 $e$와 $n$을 공유(정확히는 공개)하였다. 엘가말에서도 $g^a$와 $g^b$가 공유된다. 그러나 Massey-omura에서는 송신자와 수신자의 정보가 아무것도 공유되지 않는다. A가 메시지 송신자, B가 수신자라고 하자. A는 가방에 메시지를 넣고, 가방을 자물쇠로 잠근 후 B에게 가방을 전달한다. 비밀 키 시스템에서는 B가 열쇠를 공유받기 때문에 가방을 열 수 있다. 공개 키 시스템에서는 잠글 수만 있는 키와 열 수만 있는 키가 다르긴 하지만, 어쨌든 B는 자신의 열쇠를 이용하여 가방을 열 수 있다. 그런데 Massey-omura에..

서명 서명이 있으면 암호화만 가지고는 못 하는 일들을 할 수 있다. 예를 들어 인터넷뱅킹. 내 입장에서 보면 상대가 은행인지 어떻게 아는가? 반대로 은행 측은 내가 계좌 주인인지 어떻게 아는가? 상대방을 확인할 수 있는 서명이 있다면, 서명이 누구의 것인지 확인할 수 있다면 많은 일을 할 수 있다. 이상적인 서명은 어때야 하는가? 단 한명만 만들 수 있는 서명, 누구나 그 서명의 주체를 확인할 수 있는 서명이 좋은 서명이다. 또, 내가 서명했다는 사실을 부인할 수 없어야 한다. RSA 서명 다음의 상황을 가정한다. $p,q$: 큰 소수 (공개됨) $n=pq$ (공개됨) $e$: 암호화 키 (공개) $d$: 복호화 키 (비공개) $ed=1\mathrm{mod}(p-1)(q-1)$ 메시지 $m$에 대해 서명 $s(m..

3000번: 직각 삼각형 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 점의 좌표가 X Y 순서대로 주어진다. (1 ≤ X,Y ≤ 100,000) 겹치는 점은 없다. www.acmicpc.net 아주 단순한 $O(N^2\log N)$짜리 풀이법을 생각할 수 있다. 빗변을 이루는 두 점을 고르고, 직각삼각형이 되기 위해 필요한 나머지 한 점이 존재하는지 찾으면 된다. 두 점을 고르는 데 $N^2$, 나머지 한 점을 찾는 데 $\log N$ 시간이 걸린다. 그러나 $N\le 100,000$이므로 이 풀이를 사용하면 시간 초과. 따라서 조금 더 빠른 풀이를 생각해야 한다. 사실 나도 꽤 오래 걸렸다. 빗변이 아닌 두 변이 좌표축에 평행해야 한다는..

저번 시간까지 RSA에 대해 공부했다. 이제 두 번째 암호에 대해 알아보자. 이산 로그 (Discrete Log) $Z_n^{\ast }=\{g,g^2,\cdots ,g^{\phi (n)}(=1)\}$이면 $g$는 $Z_n^{\ast }$의 Generator이다. Generator가 항상 존재하지는 않는다. 예를 들어 $Z_{15}^{\ast }$의 Generator는 존재하지 않는다. 사실 Generator가 존재할 조건은 다음과 같다. $Z_n^{\ast }$의 Generator가 존재한다 $\iff n=2,2^2,p^k,2p^k$, $p$는 홀수 소수 $Z_7^{\ast }=\{1,2,3,4,5,6\}$의 Generator $g=3$..

소인수분해는 얼마나 어려운가? RSA를 뚫는 것은 $n$을 소인수분해(factoring)하는 문제와 동치임을 보였다. 그러면 소인수분해는 얼마나 어려운가? 지금까지 알려진 바에 의하면 소인수분해는 $NP\cap co-NP$에 속한다. 그러나 소인수분해가 $P$에 속하는지는 알려지지 않았다. 추측하기로는 $P$에는 속하지 않고, $NP\cap co-NP$에 속하지 않을까 싶다. 소인수분해와 소수 확인 (Primality) 더보기 # 소인수분해와 소수 (펼치기) 소인수분해를 하면 소수인지 확인할 수 있다. 그러나 소수인지 아닌지 안다고해서 소인수분해가 가능한 것은 아니다. 소수가 아니라면 그 수의 소인수를 찾아야 하기 때문이다. 위에서 말했듯이 소인수분해는 $P$에 있는지 알려지지 않았다. $n$이 소수..