<div id="readability-page-1" class="page"><div>
 
 <article>
 <ul id="markdown-toc">
 <li><a href="#카이사르-암호" id="markdown-toc-카이사르-암호">카이사르 암호</a> <ul>
 <li><a href="#암호화" id="markdown-toc-암호화">암호화</a></li>
 <li><a href="#복호화" id="markdown-toc-복호화">복호화</a></li>
 <li><a href="#코드로-구현해보자" id="markdown-toc-코드로-구현해보자">코드로 구현해보자</a></li>
 </ul>
 </li>
 <li><a href="#rot13" id="markdown-toc-rot13">ROT13</a> <ul>
 <li><a href="#vim의-g" id="markdown-toc-vim의-g">Vim의 g?</a></li>
 <li><a href="#tr-명령어를-사용하기" id="markdown-toc-tr-명령어를-사용하기">tr 명령어를 사용하기</a></li>
 </ul>
 </li>
 <li><a href="#아핀-암호" id="markdown-toc-아핀-암호">아핀 암호</a> <ul>
 <li><a href="#아핀-암호의-해독" id="markdown-toc-아핀-암호의-해독">아핀 암호의 해독</a></li>
 <li><a href="#글자-빈도-검사를-통한-아핀-암호의-해독" id="markdown-toc-글자-빈도-검사를-통한-아핀-암호의-해독">글자 빈도 검사를 통한 아핀 암호의 해독</a></li>
 </ul>
 </li>
 <li><a href="#참고문헌" id="markdown-toc-참고문헌">참고문헌</a></li>
 <li><a href="#함께-읽기" id="markdown-toc-함께-읽기">함께 읽기</a></li>
 <li><a href="#주석" id="markdown-toc-주석">주석</a></li>
</ul>

<h2 id="카이사르-암호">카이사르 암호</h2>

<ul>
 <li>카이사르 암호는 로마의 Julius Caesar가 사용했다고 전해지는 암호 시스템이다.</li>
 <li>각 알파벳을 세 글자 차이나는 글자로 치환하는 방식.
 <ul>
 <li>예: A를D로, X를 A로 바꾸는 방식.</li>
 </ul>
 </li>
</ul>

단순히 알파벳의 자리를 옮기는 방식이기 때문에 자리이동식 암호법(shift cipher)이라고도 부른다.

<h3 id="암호화">암호화</h3>

각 알파벳을 $[0, 25]$ 범위의 정수로 생각하면 암호화 방법을 다음과 같이 표현할 수 있다.

\[f(p) = (p + 3) \bmod 26\]

<h3 id="복호화">복호화</h3>

$f$ 의 역함수 $f^{-1}$를 사용하면 암호문을 복호화할 수 있다.

\[f^{-1}(p) = (p - 3) \bmod 26\]

<h3 id="코드로-구현해보자">코드로 구현해보자</h3>

<code>%</code> 연산자를 쓰기 곤란하므로 <code>mod</code> 함수부터 구현하자.

<ul>
 <li><code>%</code> 연산자가 부호를 무시하고 나머지를 구하기 때문이다.
 <ul>
 <li>나머지는 항상 양수여야 하는데, 음수가 나오므로 그대로 사용하기 곤란하다.</li>
 <li>가령 <code>-13 % 4</code>의 결과로 <code>3</code> 이 나와야 하는데 <code>-1</code> 이 나온다.</li>
 </ul>
 </li>
</ul>

<div><pre><code>Number.prototype.mod = function(n) {
 return ((this % n) + n) % n;
}
</code></pre></div>

암호문으로 대문자만 사용한다는 전제 하에 몇 가지 상수를 정의하자.

<div><pre><code>// A: 65, Z: 90
const PADDING = 65;
const LIMIT = 90;
const N = 26;
const KEY = 3;
</code></pre></div>

대문자만 다룰 것이므로, 식별하는 함수도 만들어 주자.

<div><pre><code>function isUpperCase(code) {
 return PADDING &lt;= code &amp;&amp; code &lt;= LIMIT;
}
</code></pre></div>

그리고 다음과 같이 암호화 알고리즘을 구현했다.

caesar 함수는 암호화와 복호화의 방식이 더하기냐 빼기냐 밖에 없기 때문에
해당 부분을 책임지는 <code>keyFunc</code>를 받아 암호/복호화하도록 하였다.

<div><pre><code>function caesar(msg, keyFunc) {
 let enc = '';
 for (var i = 0; i &lt; msg.length; i++) {
 const code = msg.charCodeAt(i);

 if (!isUpperCase(code)) {
 enc += msg[i];
 continue;
 }

 const original = code - PADDING;
 const encrypted = keyFunc(original).mod(N);
 enc += String.fromCharCode(encrypted + PADDING);
 }
 return enc;
}
</code></pre></div>

암/복호화 여부를 결정하는 함수도 만들어 주었다.

<div><pre><code>function encrypt(num) {
 return num + KEY;
}

function decrypt(num) {
 return num - KEY;
}
</code></pre></div>

실행하면 다음과 같은 결과가 나온다.

<div><pre><code>enc = caesar("MEET YOU IN THE PARK", encrypt);
// "PHHW BRX LQ WKH SDUN"

caesar(enc, decrypt);
// "MEET YOU IN THE PARK"
</code></pre></div>

<h2 id="rot13">ROT13</h2>

<blockquote>

 각 문자를 13자리씩 밀어내 치환하고 끝에 도달하면 앞으로 돌아가는 방식도 있다.
이 암호는 로트13(rot13)이라 하는데, 회전을 의미하는 영어 단어 rotate를 줄여서 붙인 이름이다.
로트13은 핵심을 찌르는 유머나 공격적인 말을 숨길 때 인터넷상에서 종종 사용된다.
이 암호들의 일반 원리는 k 자리만큼 문자를 이동하는 것이다.
즉 모듈로 26에 대해 k를 더하는 방식이다.
이를 일반적으로 키 값이 k인 이동 암호(shift cipher) 또는 덧셈 암호(additive cipher)라 한다.
<a href="#fn:josh-6" rel="footnote">1</a>
</blockquote>

<h3 id="vim의-g">Vim의 g?</h3>

Vim의 <code>g?</code>를 사용하면 간편하게 ROT13 방식의 암호화를 할 수 있다.

예를 들어 <code>abcd</code>를 visual 모드로 선택한 다음, <code>g?</code>를 입력하면 <code>nopq</code>로 암호화된다.

<code>Hello World</code>는 <code>Uryyb Jbeyq</code>가 된다.

다음은 <code>:help g?</code>를 인용한 것이다.

<div><pre><code>							*g?* *rot13*
g?{motion}		Rot13 encode {motion} text.

							*v_g?*
{Visual}g?		Rot13 encode the highlighted text (for {Visual} see
			|Visual-mode|).

g?g?							*g?g?* *g??*
g??			Rot13 encode current line.
</code></pre></div>

<h3 id="tr-명령어를-사용하기">tr 명령어를 사용하기</h3>

[[/cmd/tr##character-1-1-replace]]{tr 명령의 1:1 문자 교체 기능}을 사용하면 간단하게 ROT13 방식의 암호화를 할 수 있다.

<div><pre><code>$ echo abcd | tr 'a-z' 'n-za-m'

nopq

$ echo 'Hello World' | tr 'A-Za-z' 'N-ZA-Mn-za-m'
Uryyb Jbeyq
</code></pre></div>

<h2 id="아핀-암호">아핀 암호</h2>

Affine cipher

다음 함수를 사용하면 카이사르 암호를 일반화할 수 있다.

\[f(p) = (ap + b) \bmod 26\]

단, 다음의 조건을 만족해야 한다.

<ul>
 <li>$a, b$ 는 정수.</li>
 <li>$\gcd(a, 26) = 1$.</li>
 <li>$f$ 는 전단사 함수(일대일 대응).</li>
</ul>

<h3 id="아핀-암호의-해독">아핀 암호의 해독</h3>

\[f(p) = (ap + b) \bmod 26 = c\\\]

p 를 암호화한 결과를 c라 하자.

c는 $ap + b$와 $\bmod 26$에서 합동이므로 다음과 같이 생각할 수 있다.

\[\begin{align}
c &amp; ≡ ap + b (\bmod 26) \\
c - b &amp; ≡ ap (\bmod 26) \\
\end{align}\]

a 모듈로 26의 역 $\bar{a}$를 알아낼 수 있다면 다음과 같이 p를 구할 수 있다.
(전제에서 $\gcd(a, 26) = 1$ 이었으므로, a 모듈로 26의 역 $\bar{a}$는 존재한다.)

\[\begin{align}
c - b &amp; ≡ ap (\bmod 26) \\
\bar{a}(c-b) &amp; ≡ a \bar{a} p (\bmod 26) \\
\bar{a}(c-b) &amp; ≡ p (\bmod 26) \\
\end{align}\]

<h3 id="글자-빈도-검사를-통한-아핀-암호의-해독">글자 빈도 검사를 통한 아핀 암호의 해독</h3>

카이사르 암호, 아핀 암호의 해독은 글자 빈도를 따져보면 풀 수 있는 경우가 많다.

다음은 알파벳 빈도를 표로 나타낸 것이다.

<table>
 <thead>
 <tr>
 <th>Letter</th>
 <th>Count</th>
 <th>Frequency</th>
 </tr>
 </thead>
 <tbody>
 <tr>
 <td>E</td>
 <td>21912</td>
 <td>12.02</td>
 </tr>
 <tr>
 <td>T</td>
 <td>16587</td>
 <td>9.10</td>
 </tr>
 <tr>
 <td>A</td>
 <td>14810</td>
 <td>8.12</td>
 </tr>
 <tr>
 <td>O</td>
 <td>14003</td>
 <td>7.68</td>
 </tr>
 <tr>
 <td>I</td>
 <td>13318</td>
 <td>7.31</td>
 </tr>
 <tr>
 <td>N</td>
 <td>12666</td>
 <td>6.95</td>
 </tr>
 <tr>
 <td>S</td>
 <td>11450</td>
 <td>6.28</td>
 </tr>
 <tr>
 <td>R</td>
 <td>10977</td>
 <td>6.02</td>
 </tr>
 <tr>
 <td>H</td>
 <td>10795</td>
 <td>5.92</td>
 </tr>
 <tr>
 <td>D</td>
 <td>7874</td>
 <td>4.32</td>
 </tr>
 <tr>
 <td>L</td>
 <td>7253</td>
 <td>3.98</td>
 </tr>
 <tr>
 <td>U</td>
 <td>5246</td>
 <td>2.88</td>
 </tr>
 <tr>
 <td>C</td>
 <td>4943</td>
 <td>2.71</td>
 </tr>
 <tr>
 <td>M</td>
 <td>4761</td>
 <td>2.61</td>
 </tr>
 <tr>
 <td>F</td>
 <td>4200</td>
 <td>2.30</td>
 </tr>
 <tr>
 <td>Y</td>
 <td>3853</td>
 <td>2.11</td>
 </tr>
 <tr>
 <td>W</td>
 <td>3819</td>
 <td>2.09</td>
 </tr>
 <tr>
 <td>G</td>
 <td>3693</td>
 <td>2.03</td>
 </tr>
 <tr>
 <td>P</td>
 <td>3316</td>
 <td>1.82</td>
 </tr>
 <tr>
 <td>B</td>
 <td>2715</td>
 <td>1.49</td>
 </tr>
 <tr>
 <td>V</td>
 <td>2019</td>
 <td>1.11</td>
 </tr>
 <tr>
 <td>K</td>
 <td>1257</td>
 <td>0.69</td>
 </tr>
 <tr>
 <td>X</td>
 <td>315</td>
 <td>0.17</td>
 </tr>
 <tr>
 <td>Q</td>
 <td>205</td>
 <td>0.11</td>
 </tr>
 <tr>
 <td>J</td>
 <td>188</td>
 <td>0.10</td>
 </tr>
 <tr>
 <td>Z</td>
 <td>128</td>
 <td>0.07</td>
 </tr>
 </tbody>
</table>

<ul>
 <li><a href="http://pi.math.cornell.edu/~mec/2003-2004/cryptography/subs/frequencies.html">자료 출처</a></li>
</ul>

<h2 id="참고문헌">참고문헌</h2>

<ul>
 <li>Rosen의 이산수학 / Kenneth H. Rosen 저 / 공은배 등저 / 한국맥그로힐(McGraw-Hill KOREA) / 2017년 01월 06일</li>
 <li><a href="http://pi.math.cornell.edu/~mec/2003-2004/cryptography/subs/frequencies.html">English Letter Frequency (based on a sample of 40,000 words)</a></li>
 <li><a href="https://en.wikipedia.org/wiki/Letter_frequency">Letter frequency</a></li>
 <li>수학으로 이해하는 암호의 원리 / 조슈아 홀던 저/허성심 역 / 프리렉 / 초판 1쇄 2017년 11월 30일 / 원제 : THE MATHEMATICS OF SECRETS: Cryptography From Caesar Ciphers To Digital Encryption</li>
</ul>

<h2 id="함께-읽기">함께 읽기</h2>

<ul>
 <li>[[/cmd/tr#character-1-1-replace]]</li>
 <li>[[/study/rosen-discrete-math-7/linear-congruences#a-모듈로-m-의-역-inverse]]{a 모듈로 m의 역}</li>
 <li>[[/study/rosen-discrete-math-7/modular]]</li>
</ul>

<h2 id="주석">주석</h2>



 </article>


 
 
 



</div></div>

카이사르 암호(Caesar cipher)

댓글