반응형
공학수학2 / 2002년2학기 / 박근수 교수님
[설명]
Vigenere Cipher and Cryptanalysis : n만큼의 길이를 가지는 Key를 이용해 암호화. 그리고 그 Key 없이 암호분석.
vigen.cpp : Key를 이용하여 Plaintext(vigen.in)를 Ciphertext(vigen.out)으로 바꿈.
vigcr.cpp : Ciphertext로부터 Key를 유추하여 Plaintext(vigcr.out)을 만들어냄.
vigen.in : 첫줄에는 Key가 있어야 함. Key는 반드시 대문자. 나머지 plaintext는 소문자.
vigen.out : <vigen> 실행시 자동 생성됨. Ciphertext.
vigcr.out : <vigcr> 실행시 자동 생성됨. 정상적으로 동작할 경우 vigen.in과 같은 파일임.
[vigen.cpp]
#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include <stdio.h>
void main()
{
char buffer[42]; // 읽어들인 스트링을 임시로 저장할 버퍼
char cipher[41] = {0}; // 변환된 스트링을 저장할 배열
char key[20]; // 키를 저장할 배열
char inputFile[] = "vigen.in";
char outputFile[] = "vigen.out";
ifstream input(inputFile);
ofstream output(outputFile); // 입출력 스트림
if (!input) {cerr << "Error in file name" << endl; return;} // 파일이 없을때
else
{
input.getline(buffer, 30); // 첫라인(키)를 읽어들임
int keylen = strlen(buffer);
if (keylen<5 || keylen>20) {cerr << "Error in Key length." << endl; return;} // 키 길이가 맞는지 검사
else
{
for(int i=0; i<keylen; i++) // 키가 전부 알파벳 대문자가 맞는지 검사
if (buffer[i]<65 || buffer[i]>91) {cerr << "Error in Key String." << endl; return;}
strcpy(key, buffer); // 다 획안되면 버퍼의 내용을 키에 복사
}
printf("Key : %s\n",key); // 키를 출력
printf("%-40s%-40s","Input : Plaintext","Output : Cyphertext");
while (!input.eof())
{
input.getline(buffer, 42); // 한 줄씩 입력 받음
int j=0;
/* 혹시 마지막줄이 40글자가 안될때를 대비해서 새로운 줄을 읽을때마다 초기화 */
for (int i=0; i<(int)strlen(cipher); i++) cipher[i] = ' ';
printf("%-40s",buffer);
for (i=0; i<(int)strlen(buffer); i++)
{
cipher[i] = (buffer[i] - 'a' + key[j++] - 'A') % 26 + 'A';
if (j>=(int)strlen(key)) j=0;
}
printf("%-40s",cipher); // 콘솔에 출력
output << cipher << endl; // 파일에 출력
}
}
char garbage;
cout << "\n\nPress Ctrl+C To End The Program.";
cin >> garbage; // 출력 결과를 볼 수 있도록 기다림.
return;
}
[vigcr.cpp]
#include <fstream.h>
#include <string.h>
#include <iostream.h>
#include <stdlib.h>
#include <math.h>
char inputFile[] = "vigen.out";
char outputFile[] = "vigcr.out";
char* cipher; // 입력받는 cipher text를 저장할 array.
int size_of_input_file(void); // input file의 크기를 계산하는 함수. (동적할당을 위해)
void read_ciphertext(void); // input을 읽는 함수.
int determine_m(int*); // 키의 길이를 결정하는 함수.
void compute_ic(int, double*); // m이 주어질 때 각 줄의 index of coincidence를 계산하는 함수.
int rel_shift(int, char*); // m값으로 배열해서, 각 Mutual IC를 이용한 Relative Shift를 수행하는 함수.
void compute_prob(double**, int); // m줄로 배열했을때, 각 줄의 알파벳 확률(MIC를 구하기 위해)을 계산하는 함수.
int compute_gap(int, int, int, double**); // 두 줄의 Mutual IC를 이용해 gap을 판단하는 함수.
char find_uni_key(void); // Relative Shift를 마친 후 하나의 키를 찾는 과정.
void main()
{
int m;
cipher = (char*)calloc(size_of_input_file(), sizeof(char));
/* 인풋파일의 크기를 미리 읽어서 cipher text를 저장할 array를 동적할당. */
read_ciphertext();
int m_except[16]; // 잘못 계산된 m (다음 계산때 제외할 m)
m = determine_m(m_except);
char* key = (char*)calloc(m+1, sizeof(char));
/* 키를 저장할 char array 선언, 할당 */
int m_ok = rel_shift(m, key); // m이 정확한지를 판단하는 값 m_ok
/* m을 이용해 relaive shift를 한다. key[]에는 첫번째 키와의 gap을 넣는다. */
while (!m_ok) // rel_shift가 올바른 값(1)을 리턴할때 까지
{
static int a = 0;
m_except[a++] = m; // 잘못계산된 m 값을 배열에 저장
m = determine_m(m_except); // 이전에 계산한 m값들을 제외하고 m 계산
m_ok = rel_shift(m, key);
}
key[0] = find_uni_key(); // 키의 첫번째 글자를 찾는다.
for (int i=1; i<m; i++)
key[i] = (key[i] + key[0] - 'A') % 26 + 'A'; // 찾아낸 첫번째 글짜를 이용해 나머지 글자를 채운다.
key[i] = '\0'; // 스트링으로 쓰기 위해 마지막에 널문자를 넣어준다.
ofstream out(outputFile);
cout << "Found Key : " << key; // 콘솔로 키를 출력.
out << key; // 파일로 키를 출력.
for (i=0; i<(int)strlen(cipher); i++) // 찾은 키를 이용해 사이퍼텍스트를 shift 시킨다.
cipher[i] = (cipher[i] - key[0] + 26) % 26 + 'a'; // gap 만큼은 이미 shift 되어 있으므로 키 첫글자 만큼만!
for (i=0; i<(int)strlen(cipher); i++)
{
if (i%40 == 0) // 한줄에 40글자씩 출력하기 위해 다음줄로...
{
cout << endl;
out << endl;
}
cout << cipher[i]; // 콘솔에 출력.
out << cipher[i]; // 파일로 출력.
}
out << endl;
free(key);
free(cipher);
char garbage;
cout << "\n\nPress Ctrl+C To End The Program.";
cin >> garbage; // 출력 결과를 볼 수 있도록 기다림.
return;
}
int size_of_input_file(void) // 인풋파일의 사이즈 계산
{
char buf[42];
int c = 0;
ifstream in(inputFile);
while(!in.eof())
{
in.getline(buf, 42);
c++; // 라인 수를 카운트
}
in.close();
return c*40; // 계산한 값을 리턴
}
void read_ciphertext()
{
char buf[42];
ifstream in(inputFile);
while(!in.eof())
{
in.getline(buf, 42);
strcat(cipher, buf); // 한줄씩 읽어서 cipher에 계속 덧붙임.
}
for (int i=0; i<(int)strlen(cipher); i++)
if (cipher[i]<'A' || cipher[i]>'Z')
{
cipher[i] = '\0';
break;
} // 입력받은 array에 알파벳을 제외한 다른 문자가 있을 경우 그곳에서 짤라서 프로그램이 정상적으로 돌아가게 함.
in.close();
return;
}
int determine_m(int* ex)
{
int candi_m, det_m = 0; // m이 될수있는 후보, 선택된 m
double ic_avg, ic_avg_max = 0; // index of coincidence의 평균, 그 평균의 최대값.
double diff, diff_min = 1; // IC와 0.065와의 차이. 그 차이의 최소값.
for (int m=5; m<=20; m++)
{
int i;
double *ic = (double*)calloc(m, sizeof(double)); // IC 값들을 저장할 배열
for(int k=0; k<16; k++)
if (ex[k] == m) goto END_OF_LOOP;
compute_ic(m, ic);
ic_avg = 0;
diff = 0;
for (i=0; i<m; i++)
{
diff += fabs(0.065-ic[i]); // 각 줄의 IC들이 0.065에서 얼마나 떨어져 있나를 알아봄.
ic_avg += ic[i];
}
free(ic);
diff = diff/m; // m개의 IC가 있으므로 균형을 맞추기 위해 m으로 나눔.
ic_avg = ic_avg/m;
if ((0.065-ic_avg) < (ic_avg-0.038)) // IC의 평균의 0.038보다 0.065에 더 가까울 때.
{
if (diff_min > diff) // diff가 최소인 값을 m으로 택한다.
{
diff_min = diff;
det_m = m;
}
}
else // 만약 0.038보다 0.065에 더 가까운 값이 없을 때.
if (ic_avg_max < ic_avg) // 평균이 가장 큰 값을 m으로 택하기 위해 후보로 둔다.
{
ic_avg_max = ic_avg;
candi_m = m;
}
END_OF_LOOP :;
}
if (det_m == 0) // det_m이 결정되지 않았을 때.
return candi_m;
else
return det_m;
}
void compute_ic(int m, double* ic) // IC를 계산하는 루틴.
{
for (int i=0; i<m; i++)
{
int n = 0;
int count[26] = {0};
while (cipher[n*m + i] >= 'A' && cipher[n*m + i] <= 'Z') // i번째 글자, (m+i)번째 글자, (2m+i)번째 글자.. 순으로 읽는다.
{
count[cipher[n*m + i]-'A']++; // 그 글자에 해당하는 카운트를 1 더한다.
n++;
}
for (int j=0; j<26; j++)
ic[i] += (double)(count[j]*(count[j]-1))/(n*(n-1)); // 카운트한 값으로 IC를 구한다.
}
}
int rel_shift(int m, char* key)
{
double **p; // MIC를 계산하기 위해 각 줄마다 알파벳이 등장할 확률을 저장할 2차원 array
p = (double**)calloc(m, sizeof(double*)); // m개의 줄 할당
for (int i=0; i<m; i++)
p[i] = (double*)calloc(26, sizeof(double)); // 각 줄마다 26개의 칸 할당
compute_prob(p, m); // 각 줄의 알파벳 확률 계산
int* gap = (int*)calloc(m, sizeof(int)); // key의 첫글자와 나머지 글자들 간의 gap을 저장할 array
for (i=1; i<m; i++)
gap[i] = compute_gap(m, 0, i, p); // 첫번째 줄 과 나머지 줄간의 gap 계산.
for (int j=2; j<m; j++) // gap이 정확한지 확인하는 루틴
{
int temp_gap = (compute_gap(m,1,j,p) + gap[1]) % 26; // key의 두번째 글자와의 gap을 계산해서 gap[1]과 더함.
if (temp_gap != gap[j]) // 만약 첫번째 계산결과와 두번째 계산결과가 다르다고 나오면...
{
int temp_gap_2 = (compute_gap(m,2,j,p) + gap[2]) % 26; // key의 세번째 글자와의 gap을 계산해서
if (temp_gap_2 == gap[j]) // 세개의 gap 중에 같은 두개의 gap을 선택!!
break;
else if (temp_gap_2 == temp_gap)
gap[j] = temp_gap;
else // 만약 세개의 gap이 모두 다르다고 나오면
{
int temp_gap_3 = (compute_gap(m,3,j,p) + gap[3]) % 26; // 한번더 계산
if (temp_gap_3 == gap[j])
break;
else if (temp_gap_3 == temp_gap)
gap[j] = temp_gap;
else if (temp_gap_3 == temp_gap_2)
gap[j] = temp_gap_2; // 넷 중에 같은 두개의 gap이 맞는 것이라고 판단!!
else
{
// 넷 모두 다르다면 키가 정확하지 않을 가능성이 많음!!
// 이 경우엔 m이 잘못 계산됐거나, 통계적으로 잘 맞지 않는 plaintext일 가능성이 높음.
free(gap);
for (i=0; i<m; i++)
free(p[i]);
free(p); // 동적할당 변수들을 모두 free
return 0; // 잘못된 결과임을 return
}
}
}
}
for (i=1; i<m; i++)
{
int n = 0;
while (cipher[n*m+i] >= 'A' && cipher[n*m+i] <= 'Z')
{
cipher[n*m+i] = (cipher[n*m+i] - 'A' - gap[i] + 26) % 26 + 'A';
n++; // 계산한 gap을 이용해서 ciphertext의 각 줄을 gap 만큼 shift
// 그렇게 되면 cipher 텍스트 전체가 한글자의 key로 shift시킨것과 같게 된다!
}
key[i] = gap[i]; // gap값을 key에 저장.
}
free(gap);
for (i=0; i<m; i++)
free(p[i]);
free(p);
return 1; // 정상적으로 return
}
void compute_prob(double** p, int m) // 각 줄의 알파벳 확률 계산
{
for (int i=0; i<m; i++)
{
int n = 0;
while (cipher[n*m+i] >= 'A' && cipher[n*m+i] <= 'Z')
{
p[i][cipher[n*m+i]-'A']++;
n++;
}
for (int j=0; j<26; j++)
p[i][j] = p[i][j] / n;
}
}
int compute_gap(int m, int i, int j, double** p) // MIC를 이용해 i와 j열 간의 gap 판단하기
{
int gap;
double mic[26] = {0};
double curr_diff, diff_min = 1; // 현재 MIC의 0.065와의 차, 그 차의 최소값.
for (int l=0; l<26; l++) // l을 0부터 25까지 돌리면서 적절한 gap을 찾는다.
{
for (int k=0; k<26; k++)
mic[l] += p[i][k] * p[j][(k+l)%26];
curr_diff = fabs(0.065 - mic[l]);
if (curr_diff < diff_min) // diff가 최소인 gap 찾는다.
{
diff_min = curr_diff;
gap = l;
}
if (curr_diff < 0.005) break; // 단 diff가 일정기준 이상으로 아주 작으면 그 값을 택한다.
}
return gap;
}
char find_uni_key() // cipher가 한글자의 key로 shift된 상태일때, 그 한글자의 key를 찾는다.
{
int count[26] = {0};
for (int i=0; i<(int)strlen(cipher); i++)
count[cipher[i]-'A']++;
int count_max = count[0];
char uni_key = ('A' - 'E' + 26) % 26 + 'A'; // 일단 key가 A라고 생각.
for (i=1; i<26; i++)
{
if (count_max < count[i])
{
count_max = count[i];
uni_key = ('A' + i - 'E' + 26) % 26 + 'A'; // count가 최대인 값이 plaintext에서 e에 해당한다고 보고 uni_key 계산
}
}
return uni_key;
}
[설명]
Vigenere Cipher and Cryptanalysis : n만큼의 길이를 가지는 Key를 이용해 암호화. 그리고 그 Key 없이 암호분석.
vigen.cpp : Key를 이용하여 Plaintext(vigen.in)를 Ciphertext(vigen.out)으로 바꿈.
vigcr.cpp : Ciphertext로부터 Key를 유추하여 Plaintext(vigcr.out)을 만들어냄.
vigen.in : 첫줄에는 Key가 있어야 함. Key는 반드시 대문자. 나머지 plaintext는 소문자.
vigen.out : <vigen> 실행시 자동 생성됨. Ciphertext.
vigcr.out : <vigcr> 실행시 자동 생성됨. 정상적으로 동작할 경우 vigen.in과 같은 파일임.
[vigen.cpp]
#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include <stdio.h>
void main()
{
char buffer[42]; // 읽어들인 스트링을 임시로 저장할 버퍼
char cipher[41] = {0}; // 변환된 스트링을 저장할 배열
char key[20]; // 키를 저장할 배열
char inputFile[] = "vigen.in";
char outputFile[] = "vigen.out";
ifstream input(inputFile);
ofstream output(outputFile); // 입출력 스트림
if (!input) {cerr << "Error in file name" << endl; return;} // 파일이 없을때
else
{
input.getline(buffer, 30); // 첫라인(키)를 읽어들임
int keylen = strlen(buffer);
if (keylen<5 || keylen>20) {cerr << "Error in Key length." << endl; return;} // 키 길이가 맞는지 검사
else
{
for(int i=0; i<keylen; i++) // 키가 전부 알파벳 대문자가 맞는지 검사
if (buffer[i]<65 || buffer[i]>91) {cerr << "Error in Key String." << endl; return;}
strcpy(key, buffer); // 다 획안되면 버퍼의 내용을 키에 복사
}
printf("Key : %s\n",key); // 키를 출력
printf("%-40s%-40s","Input : Plaintext","Output : Cyphertext");
while (!input.eof())
{
input.getline(buffer, 42); // 한 줄씩 입력 받음
int j=0;
/* 혹시 마지막줄이 40글자가 안될때를 대비해서 새로운 줄을 읽을때마다 초기화 */
for (int i=0; i<(int)strlen(cipher); i++) cipher[i] = ' ';
printf("%-40s",buffer);
for (i=0; i<(int)strlen(buffer); i++)
{
cipher[i] = (buffer[i] - 'a' + key[j++] - 'A') % 26 + 'A';
if (j>=(int)strlen(key)) j=0;
}
printf("%-40s",cipher); // 콘솔에 출력
output << cipher << endl; // 파일에 출력
}
}
char garbage;
cout << "\n\nPress Ctrl+C To End The Program.";
cin >> garbage; // 출력 결과를 볼 수 있도록 기다림.
return;
}
[vigcr.cpp]
#include <fstream.h>
#include <string.h>
#include <iostream.h>
#include <stdlib.h>
#include <math.h>
char inputFile[] = "vigen.out";
char outputFile[] = "vigcr.out";
char* cipher; // 입력받는 cipher text를 저장할 array.
int size_of_input_file(void); // input file의 크기를 계산하는 함수. (동적할당을 위해)
void read_ciphertext(void); // input을 읽는 함수.
int determine_m(int*); // 키의 길이를 결정하는 함수.
void compute_ic(int, double*); // m이 주어질 때 각 줄의 index of coincidence를 계산하는 함수.
int rel_shift(int, char*); // m값으로 배열해서, 각 Mutual IC를 이용한 Relative Shift를 수행하는 함수.
void compute_prob(double**, int); // m줄로 배열했을때, 각 줄의 알파벳 확률(MIC를 구하기 위해)을 계산하는 함수.
int compute_gap(int, int, int, double**); // 두 줄의 Mutual IC를 이용해 gap을 판단하는 함수.
char find_uni_key(void); // Relative Shift를 마친 후 하나의 키를 찾는 과정.
void main()
{
int m;
cipher = (char*)calloc(size_of_input_file(), sizeof(char));
/* 인풋파일의 크기를 미리 읽어서 cipher text를 저장할 array를 동적할당. */
read_ciphertext();
int m_except[16]; // 잘못 계산된 m (다음 계산때 제외할 m)
m = determine_m(m_except);
char* key = (char*)calloc(m+1, sizeof(char));
/* 키를 저장할 char array 선언, 할당 */
int m_ok = rel_shift(m, key); // m이 정확한지를 판단하는 값 m_ok
/* m을 이용해 relaive shift를 한다. key[]에는 첫번째 키와의 gap을 넣는다. */
while (!m_ok) // rel_shift가 올바른 값(1)을 리턴할때 까지
{
static int a = 0;
m_except[a++] = m; // 잘못계산된 m 값을 배열에 저장
m = determine_m(m_except); // 이전에 계산한 m값들을 제외하고 m 계산
m_ok = rel_shift(m, key);
}
key[0] = find_uni_key(); // 키의 첫번째 글자를 찾는다.
for (int i=1; i<m; i++)
key[i] = (key[i] + key[0] - 'A') % 26 + 'A'; // 찾아낸 첫번째 글짜를 이용해 나머지 글자를 채운다.
key[i] = '\0'; // 스트링으로 쓰기 위해 마지막에 널문자를 넣어준다.
ofstream out(outputFile);
cout << "Found Key : " << key; // 콘솔로 키를 출력.
out << key; // 파일로 키를 출력.
for (i=0; i<(int)strlen(cipher); i++) // 찾은 키를 이용해 사이퍼텍스트를 shift 시킨다.
cipher[i] = (cipher[i] - key[0] + 26) % 26 + 'a'; // gap 만큼은 이미 shift 되어 있으므로 키 첫글자 만큼만!
for (i=0; i<(int)strlen(cipher); i++)
{
if (i%40 == 0) // 한줄에 40글자씩 출력하기 위해 다음줄로...
{
cout << endl;
out << endl;
}
cout << cipher[i]; // 콘솔에 출력.
out << cipher[i]; // 파일로 출력.
}
out << endl;
free(key);
free(cipher);
char garbage;
cout << "\n\nPress Ctrl+C To End The Program.";
cin >> garbage; // 출력 결과를 볼 수 있도록 기다림.
return;
}
int size_of_input_file(void) // 인풋파일의 사이즈 계산
{
char buf[42];
int c = 0;
ifstream in(inputFile);
while(!in.eof())
{
in.getline(buf, 42);
c++; // 라인 수를 카운트
}
in.close();
return c*40; // 계산한 값을 리턴
}
void read_ciphertext()
{
char buf[42];
ifstream in(inputFile);
while(!in.eof())
{
in.getline(buf, 42);
strcat(cipher, buf); // 한줄씩 읽어서 cipher에 계속 덧붙임.
}
for (int i=0; i<(int)strlen(cipher); i++)
if (cipher[i]<'A' || cipher[i]>'Z')
{
cipher[i] = '\0';
break;
} // 입력받은 array에 알파벳을 제외한 다른 문자가 있을 경우 그곳에서 짤라서 프로그램이 정상적으로 돌아가게 함.
in.close();
return;
}
int determine_m(int* ex)
{
int candi_m, det_m = 0; // m이 될수있는 후보, 선택된 m
double ic_avg, ic_avg_max = 0; // index of coincidence의 평균, 그 평균의 최대값.
double diff, diff_min = 1; // IC와 0.065와의 차이. 그 차이의 최소값.
for (int m=5; m<=20; m++)
{
int i;
double *ic = (double*)calloc(m, sizeof(double)); // IC 값들을 저장할 배열
for(int k=0; k<16; k++)
if (ex[k] == m) goto END_OF_LOOP;
compute_ic(m, ic);
ic_avg = 0;
diff = 0;
for (i=0; i<m; i++)
{
diff += fabs(0.065-ic[i]); // 각 줄의 IC들이 0.065에서 얼마나 떨어져 있나를 알아봄.
ic_avg += ic[i];
}
free(ic);
diff = diff/m; // m개의 IC가 있으므로 균형을 맞추기 위해 m으로 나눔.
ic_avg = ic_avg/m;
if ((0.065-ic_avg) < (ic_avg-0.038)) // IC의 평균의 0.038보다 0.065에 더 가까울 때.
{
if (diff_min > diff) // diff가 최소인 값을 m으로 택한다.
{
diff_min = diff;
det_m = m;
}
}
else // 만약 0.038보다 0.065에 더 가까운 값이 없을 때.
if (ic_avg_max < ic_avg) // 평균이 가장 큰 값을 m으로 택하기 위해 후보로 둔다.
{
ic_avg_max = ic_avg;
candi_m = m;
}
END_OF_LOOP :;
}
if (det_m == 0) // det_m이 결정되지 않았을 때.
return candi_m;
else
return det_m;
}
void compute_ic(int m, double* ic) // IC를 계산하는 루틴.
{
for (int i=0; i<m; i++)
{
int n = 0;
int count[26] = {0};
while (cipher[n*m + i] >= 'A' && cipher[n*m + i] <= 'Z') // i번째 글자, (m+i)번째 글자, (2m+i)번째 글자.. 순으로 읽는다.
{
count[cipher[n*m + i]-'A']++; // 그 글자에 해당하는 카운트를 1 더한다.
n++;
}
for (int j=0; j<26; j++)
ic[i] += (double)(count[j]*(count[j]-1))/(n*(n-1)); // 카운트한 값으로 IC를 구한다.
}
}
int rel_shift(int m, char* key)
{
double **p; // MIC를 계산하기 위해 각 줄마다 알파벳이 등장할 확률을 저장할 2차원 array
p = (double**)calloc(m, sizeof(double*)); // m개의 줄 할당
for (int i=0; i<m; i++)
p[i] = (double*)calloc(26, sizeof(double)); // 각 줄마다 26개의 칸 할당
compute_prob(p, m); // 각 줄의 알파벳 확률 계산
int* gap = (int*)calloc(m, sizeof(int)); // key의 첫글자와 나머지 글자들 간의 gap을 저장할 array
for (i=1; i<m; i++)
gap[i] = compute_gap(m, 0, i, p); // 첫번째 줄 과 나머지 줄간의 gap 계산.
for (int j=2; j<m; j++) // gap이 정확한지 확인하는 루틴
{
int temp_gap = (compute_gap(m,1,j,p) + gap[1]) % 26; // key의 두번째 글자와의 gap을 계산해서 gap[1]과 더함.
if (temp_gap != gap[j]) // 만약 첫번째 계산결과와 두번째 계산결과가 다르다고 나오면...
{
int temp_gap_2 = (compute_gap(m,2,j,p) + gap[2]) % 26; // key의 세번째 글자와의 gap을 계산해서
if (temp_gap_2 == gap[j]) // 세개의 gap 중에 같은 두개의 gap을 선택!!
break;
else if (temp_gap_2 == temp_gap)
gap[j] = temp_gap;
else // 만약 세개의 gap이 모두 다르다고 나오면
{
int temp_gap_3 = (compute_gap(m,3,j,p) + gap[3]) % 26; // 한번더 계산
if (temp_gap_3 == gap[j])
break;
else if (temp_gap_3 == temp_gap)
gap[j] = temp_gap;
else if (temp_gap_3 == temp_gap_2)
gap[j] = temp_gap_2; // 넷 중에 같은 두개의 gap이 맞는 것이라고 판단!!
else
{
// 넷 모두 다르다면 키가 정확하지 않을 가능성이 많음!!
// 이 경우엔 m이 잘못 계산됐거나, 통계적으로 잘 맞지 않는 plaintext일 가능성이 높음.
free(gap);
for (i=0; i<m; i++)
free(p[i]);
free(p); // 동적할당 변수들을 모두 free
return 0; // 잘못된 결과임을 return
}
}
}
}
for (i=1; i<m; i++)
{
int n = 0;
while (cipher[n*m+i] >= 'A' && cipher[n*m+i] <= 'Z')
{
cipher[n*m+i] = (cipher[n*m+i] - 'A' - gap[i] + 26) % 26 + 'A';
n++; // 계산한 gap을 이용해서 ciphertext의 각 줄을 gap 만큼 shift
// 그렇게 되면 cipher 텍스트 전체가 한글자의 key로 shift시킨것과 같게 된다!
}
key[i] = gap[i]; // gap값을 key에 저장.
}
free(gap);
for (i=0; i<m; i++)
free(p[i]);
free(p);
return 1; // 정상적으로 return
}
void compute_prob(double** p, int m) // 각 줄의 알파벳 확률 계산
{
for (int i=0; i<m; i++)
{
int n = 0;
while (cipher[n*m+i] >= 'A' && cipher[n*m+i] <= 'Z')
{
p[i][cipher[n*m+i]-'A']++;
n++;
}
for (int j=0; j<26; j++)
p[i][j] = p[i][j] / n;
}
}
int compute_gap(int m, int i, int j, double** p) // MIC를 이용해 i와 j열 간의 gap 판단하기
{
int gap;
double mic[26] = {0};
double curr_diff, diff_min = 1; // 현재 MIC의 0.065와의 차, 그 차의 최소값.
for (int l=0; l<26; l++) // l을 0부터 25까지 돌리면서 적절한 gap을 찾는다.
{
for (int k=0; k<26; k++)
mic[l] += p[i][k] * p[j][(k+l)%26];
curr_diff = fabs(0.065 - mic[l]);
if (curr_diff < diff_min) // diff가 최소인 gap 찾는다.
{
diff_min = curr_diff;
gap = l;
}
if (curr_diff < 0.005) break; // 단 diff가 일정기준 이상으로 아주 작으면 그 값을 택한다.
}
return gap;
}
char find_uni_key() // cipher가 한글자의 key로 shift된 상태일때, 그 한글자의 key를 찾는다.
{
int count[26] = {0};
for (int i=0; i<(int)strlen(cipher); i++)
count[cipher[i]-'A']++;
int count_max = count[0];
char uni_key = ('A' - 'E' + 26) % 26 + 'A'; // 일단 key가 A라고 생각.
for (i=1; i<26; i++)
{
if (count_max < count[i])
{
count_max = count[i];
uni_key = ('A' + i - 'E' + 26) % 26 + 'A'; // count가 최대인 값이 plaintext에서 e에 해당한다고 보고 uni_key 계산
}
}
return uni_key;
}
반응형