알고리즘 & 자료구조 (13) 썸네일형 리스트형 [암호학] 단일치환 암호_곱셈 암호 곱셈 암호(Multiplicative Cipher) - 문자에 일정한 수(Key)를 곱해서 암호를 생성하는 방식 모듈러 연산 (Modular Arithmetic) - 모듈러 연산 "mod n" 에서 모듈러 곱셈이 역원을 갖기 위한 조건은 모듈러스 n과 서로소인 수만 역원을 가질 수 있 다. - 알파벳의 경우 mod 26 인 집합 Z26 = {0, 1, 2...25} 에서 26과 임의의 수 K의 최대공약수가 1이되면 이들은 서로소가 되고 K는 모듈러 곱셈의 역원을 갖게 된다. 즉, 1, 3, 5, 7, 9, 11, 15,17,19, 21,23, 25 를 Key 로 사용할 수 있다. /// /// 곱셈 암호 /// public class MultiCipher { public static string Encr.. [암호학] 단일치환 암호_랜덤 치환 암호 랜덤 치환 암호(Random Substitution Cipher) - 각 문자마다 랜덤하게 다른 문자를 대응시킨 암호 - 외부에서 랜덤 키를 제공받거나 자체적으로 랜덤 키 테이블을 생성해서 메시지를 암호화, 복호화한다. - 'A~Z 배열'로부터 랜덤하게 문자 하나를 선택해서 이를 순차적으로 매핑 테이블에 저장 > 배열 삭제 후 다음 문자열을 매핑 테이블에 저장 > 모든 문자를 매핑 테이블에 저장할 때 까지 반복 public class RandomCipher { // 랜덤 매핑 테이블 private readonly char[] table; public RandomCipher(string keyTable = null) { // 외부에서 키를 제공할 경우 그 키를 사용 if (keyTable != null) .. [암호학] 단일치환 암호_ROT13 암호 - 알파벳 문자를 13번 Shift 하여 암/복호화를 수행하는 방식 - Shift Key가 13인 시저암호 - A~Z 문자에 대해 NOPQRTUVWXYZABCDEFGHIJKLM 인 매핑텡이블을 갖는다. public class ROT13Cipher { // ROT13 매핑테이블 private static string ROT = "NOPQRSTUVWXYZABCDERGHIJKLM"; public static string Encrypt(string message) { return Rotate(message); } public static string Decrypt(string cipher) { return Rotate(cipher); } private static string Rotate(string str) .. [암호학] 단일치환 암호_시저암호 - 치환 암호(Substitution Cipher) : 평문의 문자를 다른 문자로 치환하는 암호 - 단일 치환 암호 : 하나의 문자가 항상 다른 하나의 문자로 매핑 랜덤한 매핑 테이블을 사용하여 치환하는 방식, 일정한 수(Key)를 더해서 암호를 생성하는 덧셈 암호, 일정한 수를 곱해 서 암호를 생성하는 곱셈 암호, 덧셈과 곱셈을 모두 사용하는 암호 등이 있다. - 시저 암호 : 문자를 일정한 간격만큼 이동하여 암호를 생성하는 방식. ex ) A는 3만큼 이동하여 D로 만들고, B를 3만큼 이동하여 E로 만드는 것과 같은 방식 송수신자는 문자를 N만큼 Shift 한다는 것(Shift Key)을 알고 있는 상태에서 메시지를 암,복호화 public class CaesarCipher { private cons.. [알고리즘] 시간복잡도(time complexity) 정리 - 코드의 실행 시간이 어떤 요인으로 결정되는지 나타나는 시간과 입력 데이터의 함수 관계. - 빅오(Big-O) 표기법 알고리즘이 겪을 수 있는 최악의 경우에 걸리는 시간과 입력 간의 상관관계 표기 입력 크기가 N이고, 이에 비례하는 시간이 걸린다면 O(N)으로 표기 * 알고리즘과 시간복잡도 알고리즘 시간 복잡도 이진 탐색 O(logN) 선형 탐색 O(N) 정렬 O(N logN) 조합 O(2^N) 순열 O(N!) 고찰 길이가 N이고 정수로 이루어진 배열에서 M개의 숫자 유무를 확인해야 한다고 가정해보자. N은 최대 10,000, M은 최대 100,000일 때, 배열을 전부 순회한다면 시간복잡도는 O(NM) 이므로 10억 이라는 결과가 나온다. 이진 탐색을 이용한다면 O((N+M)logN)의 시간복잡.. 이전 1 2 다음
