** 학교 과제 일부이며, 본 코드는 chat GPT의 도움을 받았습니다.
** 답안에 사용된 아이디어는 gpt가 아닌 제 생각이기에 정확하지 않습니다.
요구 사항
1) 키워드 7개 ~10개 사이로 구성된 한 문장을 생성하는 기능을 작성하시오.
2) 생성된 문장(평문)에 시저 암호를 적용하여 암호문을 생성하는 기능을 작성하시오.
3) 생성된 암호문을 대상으로 암호를 해독하여 평문으로 복호화 할 수 있는 일종의 해독기 기능을 작성하시오.
4) 위 내용을 100회 반복 후 암호문을 복호화 하는데 걸리는 평균 시간을 측정하여 성능 분석 을 진행하시오.
진행 방법
1) 위의 요구사항을 만족하는 c언어 코드를 작성한다.
2) 단어 값들을 가지고 있는 txt 파일을 작성한다.
3) 작성한 c 파일을 디버깅한다.
4) 각 케이스 별로 100회 테스트를 진행하고 관찰한다.
생각해낸 답안
복호화된 문장을 시프트 1~25 순서대로 시프트 해나가며 원래 문장 전체 문장과 복호화 문장 을 비교하여 찾아낸다.
➔ 원래 문장 전체를 모르는 상태에서 복호화된 문장이 맞는 지 안 맞는 지 확인해야겠다고 생각
대안 1. 복호화 된 문장에 txt 파일에 존재하는 단어가 하나라도 있으면 복호화가 완료되었다고 가정한다.
➔ 단어가 중복되었거나, 우연의 일치로 맞는 경우가 있기에 txt 파일에 있는 단어로 모두 구성되어 있는 지 여부를 확인해봐야겠다고 생각
대안 2
복호화 후보군 문장에서 txt 파일 안에 있는 단어를 찾아내 하나 둘 씩 찾아내어 지워 나간다.
모두 지워지면 복호화된 문장이라고 생각한다.
➔ 이 대안으로 최종적으로 코드를 작성
프로그래밍 언어는 C언어로 구현을 하였습니다.
크게 설계 과정은 3가지로 나누었습니다.
1. 종류에 따른 무작위 암호 생성
1) 7~10 사이의 랜덤 값, 단어 개수를 받았습니다.
2) 파일에서 한 줄씩(한 줄에 한 단어)를 읽어 단어를 문자열 배열로 관리하도록 하였습니다. 문자열 배열 값은 문자열 길이 기준으로 내림차순으로 정리하였습니다. 후보군과 비교할 때, 길이가 긴 문자열부터 문장의 존재여부를 확인하기 위함입니다. (예: high, hi => high가 포함된 건데, hi로 인식해 gh 만 남는 경우 방지)
3) 문자열 배열 중 랜덤으로 문자열을 뽑아내 랜덤 개수의 단어를 이어붙여 한 문장(패스워드)를 생성하였습니다.
2. 키 값 생성
평문의 작업단위를 랜덤 값 (5~10) 사이로 결정합니다.
중복없는 문자열로 key를 관리합니다.
3. 암호화
Plain(평문, txt 단어를 통해 생성한 문자열)과 key값, 암호화문장을 보내 encrypt 함수를 호출하여 암호화문장을 얻어옵니다.
행렬을 순서대로 생성하고 key값에 맞춰 행의 순서를 변경합니다.
변경된 행렬을 열 단위로 하나의 문자열(암호화된 문장)으로 관리합니다.
작업 단위를 맞추기 위해 빈 부분은 z를 추가해 정해진 열 단위로 표현합니다.
4. 복호화
1) 중복없는 key(문자열 순열)을 만듭니다. 암호문의 작업단위는 5~9 사이로, for문을 통해 검사를 진행하였습니다.
2) 암호문에 모든 key를 대입해가며 복호화 후보군을 생성해냈습니다. Key 값을 모르는 상태로 모든 경우의 수를 넣어 복호화 후보군을 생성하였습니다.
3) 생성해낸 후보군은 복호화 여부 검사를 하게 됩니다. 복호화가 완료되면 실행 횟수가 1 증가됩니다.
3-1) 이 때 복호화 검사는 각 후보군 문장마다 하게 됩니다. 후보군 문장 구성이 txt 파일의 단어로 모두 구성이 되어있는지 검사합니다.
3-2) 미리 생성해둔 문자열 배열(txt 단어 배열)의 값을 순서대로(문자열의 길이가 긴) 후보군 문장에 해당 단어가 존재하면 지워나갑니다. 각 후보군마다 문자열 배열의 모든 단어를 검사하여 단어 포함 여부에 따라 지워나갔을 때, 모두 다 사라진다면 복호화가 된 문장이라고 인식을 하였습니다.
3. 각 케이스 별로 100회 테스트
케이스 별로 100회씩 테스트를 하도록, 복호화 완료 할 때마다 숫자를 카운트 하였습니다.
카운트한 숫자가 100이 되면 전치 암호 생성을 멈추고 새로운 케이스 유형을 선택하게 됩니다.
4. 문제 해결 과정
1. txt 파일 생성
2. 단어를 파일 입출력으로 읽어들여 문자열 배열로 관리
3. 몇 번째 케이스 인지, 생성된 key값, 생성된 문자열의 길이와, 문자열 내용을 출력한다.
4. 암호화된 문자열을 출력한다.
행렬 생성과 행렬 재배열(행의 순서를 변경)이 잘 되었음을 알 수 있다.
5. 복호화 후보군은 이러하다.(일부 캡쳐)
6. 복호화 후보군에서 txt 파일에 존재하는 단어를 찾았을 때 삭제하나간다.
7. 다 삭제되었을 경우 복호화가 완료되었다고 가정하고 복호화된 문자열과 key값을 출력한다.측정시간을 출력한다. 위 예시를 보면 key값과 평문과 복호화된 문자열이 같은 것을 알 수 있다.
8. 총 소요시간과 평균 시간을 알려준다.
총 소요시간 : 205초 (약 3분), 평균시간 : 약 20초
5. 결과 / 결과 분석
총 100회 시행을 하였고 총 소요시간은 205.51s, 평균은 20.551 s 가 소요되었습니다.
해당 결과가 도출된 이유
Txt 파일에 존재하는 단어 기반으로 문장을 구성하고 문장을 전치 암호를 이용하여 암호화하고 복호화 후보군을 생성하였다. 복호화 여부는 복호화 후보군 문장이 txt 파일에 존재하는 단어의 구성으로 되어있는 문장인지 확인을 하였다. 그래서 시간이 적게 들었던 것 같다.
소스코드
시저암호
//#define _CRT_SECURE_NO_WARNINGS
//#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//#include <time.h>
//#include <ctype.h>
//
//#define LENGTH 200
//char encrpty[LENGTH]; // 암호화된 문자열
//char real[LENGTH]; // 원래 문자열
//char* str[LENGTH]; // txt 파일 단어(문자열) 배열
//int change = 0; // 검사 횟수
//clock_t start, end;
//double result, total_time = 0;
//int file_i;
//int check = 0;
//void RemoveString(char* ap_str, char* ap_remove_str) // 문자열에서 특정 단어 삭제하는 함수
//{
// int len;
// char* p_pos;
// while (*ap_str) {
// if (*ap_str++ == *ap_remove_str) {
// for (len = 1; *(ap_remove_str + len); len++) {
// if (*ap_str++ != *(ap_remove_str + len)) break;
// }
// if (*(ap_remove_str + len) == 0) {
// ap_str -= len;
// for (p_pos = ap_str; *(p_pos + len); p_pos++) *p_pos = *(p_pos + len);
// *p_pos = 0;
// }
// }
// }
//}
//int sort(const void* compare1, const void* compare2) { // 비교 함수 정의
// return strlen(*(const char**)compare1) - strlen(*(const char**)compare2); // strcmp로 간단히 길이 비교 가능
//}
//
//
//int decrpty(char* line, int key)
//{
// char dreal[LENGTH];
// char creal[LENGTH];
// strcpy(dreal, line);
// key = key * (-1);
// for (int i = 0; i < strlen(line); i++) {
//
// if (line[i] >= 'A' && line[i] <= 'Z') {
//
// line[i] -= 'A';
//
// if (line[i] + key < 0) {
//
// line[i] += 26;
//
// }
//
// line[i] = (line[i] + key) % 26;
//
// line[i] += 'A';
//
// }
//
// if (line[i] >= 'a' && line[i] <= 'z') {
//
// line[i] -= 'a';
//
// if (line[i] + key < 0) {
//
// line[i] += 26;
//
// }
//
// line[i] = (line[i] + key) % 26;
//
// line[i] += 'a';
//
// }
//
// } // 복호화 후보군 생성 완료
//
// strcpy(creal, line); //line 문장을 담아둔다.
//
// for (int len = file_i - 1; len >= 0; len--)
// {
// RemoveString(line, str[len]);
// // txt 단어를 포함하고 있다면 문자열에서 단어 제거
//
// }
//
//
// if (strlen(line) == 0) {
// strcpy(line, creal);
// printf("\n복호화된 문자열 : %s\n", real);
// end = clock(); //시간 측정 끝
// result = (double)(end - start);
// result /= 1000;
// printf("\n측정시간 : %f 초\n", result);
// printf("\nrandom password : %s\n시저 암호화, 복호화 완료\n\n", line);
// total_time += result; // 총 측정 시간
// return 1;
// }
//
// strcpy(line, dreal);
// return 0;
//}
//void Encrpty(char encrpty[], int key) { // 암호화
//
// for (int i = 0; i < strlen(encrpty); i++) {
// if (encrpty[i] >= 'A' && encrpty[i] <= 'Z') {
// encrpty[i] -= 'A';
// if (encrpty[i] + key < 0) {
// encrpty[i] += 26;
// }
//
// encrpty[i] = (encrpty[i] + key) % 26;
// encrpty[i] += 'A';
// }
//
// if (encrpty[i] >= 'a' && encrpty[i] <= 'z') {
// encrpty[i] -= 'a';
// if (encrpty[i] + key < 0) {
//
// encrpty[i] += 26;
//
// }
//
// encrpty[i] = (encrpty[i] + key) % 26;
//
// encrpty[i] += 'a';
//
// }
//
// }
//
//}
//int main()
//
//{
// FILE* fp1;
// char line[LENGTH];
// char c;
//
// fp1 = fopen("random.txt", "r"); // 텍스트 파일 오픈
//
// while (change < 100) {
//
// start = clock(); //시간 측정 시작
// printf("---------------------------------------");
// printf("\n%d 번째 ", change + 1);
// srand(time(NULL) + change); // 매번 다른 시드값 생성
// int len = rand() % 4 + 7; // 7~10 사이 랜덤 값;
//
// int cnt = 0;
//
//
// while (fgets(line, LENGTH - 1, fp1)) // 파일에서 단어를 읽어 문장을 생성한다.
// {
// str[file_i] = (char*)malloc(strlen(line) + 1);
// strcpy(str[file_i], line);
// str[file_i][strlen(str[file_i]) - 1] = 0;
// file_i++;
// }
// qsort(str, file_i, sizeof(char*), sort);
// // stdlib.h의 Quick sort 함수. 문자열 길이 내림차순 정리,
// //문장이 긴 단어부터 비교하도록
//
// for (int j = 0; j < len; j++)
// {
// int index = rand() % file_i;
// for (int k = 0; k < strlen(str[index]); k++) {
// encrpty[cnt] = str[index][k];
// cnt++;
// }
// }
// encrpty[cnt] = 0; // 랜덤 문자열 생성
//
//
// strcpy(real, encrpty); // 랜덤으로 생성된 문자열 저장
// printf("생성된 문자열 : %s\n\n", real);
// int key = rand() % 20 + 1;
//
//
// printf("%d번 시프트, 랜덤 %d 개의 단어 암호화 중 .... \n", key, len);
//
// Encrpty(encrpty, key); // 암호화 함수
//
// printf("\n암호화된 문자열: %s\n", encrpty);
//
// for (int k = 1; k < 25; k++) {
//
// if (decrpty(encrpty, k)) break; //복호화
// }
// change++;
//
// }
// printf("\n총 소요시간 : %f s, 평균 :%f s", total_time, total_time / 100);
// return 0;
//
//}전치암호
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <ctype.h>
#include <stdlib.h>
#define MAX_LEN 200
int change = 0; // 검사 횟수
clock_t start, end;
double result, total_time = 0;
int file_i;
char* str[MAX_LEN]; // txt 파일 단어(문자열) 배열
int check = 0;
void encrypt(char* plain, char* key, char* cipher) {
int len_plain = strlen(plain);
int len_key = strlen(key);
int rows = len_plain / len_key;
if (len_plain % len_key != 0) {
rows++;
}
char** matrix = (char**)malloc(rows * sizeof(int*));
for (int i = 0; i < rows; i++) {
matrix[i] = (char*)malloc(len_key * sizeof(char));
}
int idx = 0;
printf("행렬생성=======\n");
// 행렬 생성
for (int i = 0; i < rows; i++) {
for (int j = 0; j < len_key; j++) {
if (idx < len_plain) {
matrix[i][j] = plain[idx];
idx++;
}
else {
matrix[i][j] = 'Z';
}
printf("%c ", matrix[i][j]);
}
printf("\n");
}
printf("행렬재배열=======\n");
// 행렬 재배열
int col_idx = 0;
for (int i = 0; i < len_key; i++) {
for (int j = 0; j < rows; j++) {
cipher[col_idx] = matrix[j][key[i] - '1'];
printf("%c ", cipher[col_idx]);
col_idx++;
}
printf("\n");
}
// 암호문 마지막에 NULL 추가
cipher[col_idx] = '\0';
}
void decrypt(char* cipher, char* key, char* plain) {
int len_cipher = strlen(cipher);
int len_key = strlen(key);
int rows = len_cipher / len_key;
if (len_cipher % len_key != 0) {
rows++;
}
char** matrix = (char**)malloc(rows * sizeof(char*));
for (int i = 0; i < rows; i++) {
matrix[i] = (char*)malloc(len_key * sizeof(char));
}
int idx = 0;
// 행렬 생성
for (int i = 0; i < len_key; i++) {
for (int j = 0; j < rows; j++) {
if (idx>len_cipher)
cipher[idx] = 'Z';
matrix[j][key[i] - '1'] = cipher[idx];
//printf("% \c ", cipher[idx]);
idx++;
}
//printf("\n");
}
//printf("\n\n");
// 행렬 재배열
idx = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < len_key; j++) {
plain[idx] = matrix[i][j];
//printf("%c ", plain[idx]);
idx++;
}
//printf("\n");
}
//printf("\n\n");
// 복호화된 평문 마지막에 NULL 추가
plain[idx] = '\0';
}
void RemoveString(char* ap_str, char* ap_remove_str) // 문자열에서 특정 단어 삭제하는 함수
{
int len;
char* p_pos;
while (*ap_str) {
if (*ap_str++ == *ap_remove_str) {
for (len = 1; *(ap_remove_str + len); len++) {
if (*ap_str++ != *(ap_remove_str + len)) break;
}
if (*(ap_remove_str + len) == 0) {
ap_str -= len;
for (p_pos = ap_str; *(p_pos + len); p_pos++) *p_pos = *(p_pos + len);
*p_pos = 0;
}
}
}
}
void Eliminate(char* str, char ch)
{
for (; *str != '\0'; str++)//종료 문자를 만날 때까지 반복
{
if (*str == ch)//ch와 같은 문자일 때
{
strcpy(str, str + 1);
str--;
}
}
}
int pick(int* bucket, int n, int bucketSize, int k, char * cipher) { // key 값 생성
int i, lastIndex, smallest, item, keyi;
char creal[MAX_LEN];
char ciphereal[MAX_LEN];
if (k == 0) {// 고를 것이 없으면 출력
// 복호화 수행
char decrypted[MAX_LEN];
char key[MAX_LEN];
for (keyi = 0; keyi < bucketSize; keyi++)
key[keyi] = bucket[keyi]+'1';
key[keyi] = 0;
// printf("key : %s\n", key);
decrypt(cipher, key, decrypted); // 복호화 후보군 생성기
//printf("%s \n", decrypted);
Eliminate(decrypted, 'Z'); // 패딩 값 삭제
strcpy(creal, decrypted); //복호화 후보군 문장을 담아둔다.
//printf("복호화 후보군 text: %s\n", decrypted);
for (int len = 0; len < file_i; len++)
{
RemoveString(decrypted, str[len]);
// txt 단어를 포함하고 있다면 문자열에서 단어 제거
//printf("%s\n", decrypted);
}
if (strlen(decrypted) ==0 && check == 0) {
//printf("real : %s\n", decrypted);
strcpy(decrypted, creal); // 삭제전 문자열로 돌아간다.
if(strlen(decrypted) != 0){
printf("\n복호화된 문자열 : %s\n", decrypted);
end = clock(); //시간 측정 끝
result = (double)(end - start);
result /= 1000;
printf("\n측정시간 : %f 초\n", result);
printf("\n찾아낸 키 값 : %s \n", key);
/*
//printf("\nrandom password : %s\n암호화, 복호화 완료\n\n", decrypted);*/
total_time += result; // 총 측정 시간
}
check = 1;
}
//strcpy(decrypted, creal); // 다시 원래 상태로 되돌려놓음
return;
}
lastIndex = bucketSize - k - 1; //picked array에서 마지막에 채워진 element의 index
smallest = 0; //순열은 매번 전체 아이템에서 시작함
for (item = smallest; item < n; item++) {
int chosen = 0; //이미 뽑혔는지를 검사하기 위한 flag변수
//처음엔 false(0)으로 둔다.
for (int j = 0; j <= lastIndex; j++) {
if (bucket[j] == item) { //item이 이미 뽑힌 상태이면
chosen = 1; //뽑힌 상태이므로 true(1)로 값을 바꾸고
break; //멈춤
}
}
if (chosen)
continue; //나왔으면 그 다음 아이템으로 넘어간다
bucket[lastIndex + 1] = item; //나오지 않은 아이템을 넣는다
pick(bucket, n, bucketSize, k - 1,cipher);
}
}
int sort(const void* compare1, const void* compare2) { // 비교 함수 정의
return strlen(*(const char**)compare2)-strlen(*(const char**)compare1); // strcmp로 간단히 길이 비교 가능
}
int main() {
char plain[MAX_LEN]; //평문
char key[MAX_LEN];
char cipher[MAX_LEN];// 암호화 문장
FILE* fp1;
char line[MAX_LEN];
char c;
fp1 = fopen("random.txt", "r");
file_i = 0;
while (fgets(line, MAX_LEN - 1, fp1))
{
line[strlen(line) - 1] = 0;
str[file_i] = (char*)malloc(strlen(line)+1);
strcpy(str[file_i], line);
file_i++;
}
qsort(str, file_i, sizeof(char*), sort);
// stdlib.h의 Quick sort 함수. 문자열 길이 내림차순 정리,
//문장이 긴 단어부터 비교하도록
while (change < 100) {
start = clock(); //시간 측정 시작
printf("---------------------------------------");
printf("\n%d 번째 ", change + 1);
srand(time(NULL) + change); // 매번 다른 시드값 생성
int len = rand() % 4 + 7; // 7~10 사이 랜덤 값;
int cnt = 0;
for (int j = 0; j < len; j++) // 평문 생성
{
int index = rand() % file_i;
for (int k = 0; k < strlen(str[index]); k++) {
plain[cnt] = str[index][k];
cnt++;
}
}
plain[cnt] = 0; // 평문 마지막에 널 값 넣어주기
printf("%s\n", plain); //평문 출력
// 키 랜덤 생성
int key_len = rand() % 5 + 5;
int klen;
for (klen = 0; klen < key_len; klen++)
{
key[klen] = (rand() % key_len)+ '1';
for (int j = 0; j < klen; j++) {
if (key[klen] == key[j]) klen--;
}
}
key[klen] = 0;
printf("key: %s\n", key);
printf("len: %d\n", key_len);
// 암호화 수행
encrypt(plain, key, cipher);
printf("Encrypted text: %s\n", cipher);
//복호화 후보군 생성
for (int n = 5; n <= 9; n++) {
check = 0;
int k = n;
int* bucket = (int*)malloc(sizeof(int) * k);
pick(bucket, n, k, k, cipher);
free(bucket);
}
change++;
}
printf("총 소요시간 : %f", total_time);
return 0;
}