공지 목록
공지글
|
<--- 지난글(4차 함수까지의 그래프 그리기 - 솔직히 좀 재미없음)인기글(이차방정식 근의 공식 계산기 - 다른 것도 좀 봐주세요!!) 안녕하세요. locha입니다. 오랜만에 돌아온 잡다한 것들인데요!! 솔직히 지난번 포스팅은 제가 생각해도 좀 재미가 없었던 것을 사실이라 이번에는 좀 재밌는 것을 해보도록 하겠습니다. 바로 RSA암호라는 것인데요. 실제로 현재 우리나라 금융 등에도 사용되고 있는 암호화 시스템인데 큰 수는 두 소수의 곱으로 소인수분해하기가 어렵다라는 원리를 기본으로 하여 만들어진 암호입니다. 재밌고 유익했다면 공감과 댓글 하나씩 남겨주시고요. 궁금한 점이나 오류 등은 댓글에 남겨주시거나 으로 메일 주시면 답변, 그리고 수정을 하도록 하겠습니다. 인트로가 길었군요!! 바로 시작해 보도록 하죠. 1977년 Ron Rivest, Adi Shamir, Leonard Adleman 이 세 사람의 성을 딴 RSA암호가 개발되었습니다. 이 암호화 시스템은 큰 수는 두 소수의 곱으로 소인수분해하기 어렵다라는 것을 기본 원리로 삼은 암호화 시스템입니다. 그럼 한번 이 RSA암호를 파이썬으로 구현해보도록 하겠습니다. 일단 결론부터 말해보도록 하죠.(증명은 생략합니다. 저는 코딩 블로거지 수학 블로거는 아니기 때문에... 증명은 이곳을 참고하시길!!) 설계 및 원리 : 1. 두 소수 p, q를 준비한다. 2. p - 1, q - 1과 모두 서로소인 정수 e를 준비한다. 이때 e는 공개키가 된다. 3. ed를 (p - 1)(q - 1)로 나눈 나머지가 1인 d를 찾는다. 이때 d는 개인키가 된다. 4. N = pq를 계산하고 N과 e를 공개한다. 암호화 : 암호문 = 평서문^e mod N 복호화 : 평서문 = 암호문^d mod N RSA는 기본적으로 요런식의 원리를 사용하여 작동합니다. 그리고 본격적으로 코딩을 하기전에 알아야 할 것이 하나 더 있는데요. 바로 두 수의 최대공약수를 구하는 좋은 방법인 유클리드 호제법입니다. 유클리드 호제법은 설계 및 원리 : 1. 두 수 a, b(a >= b)를 준비한다. 2. r = a mod b를 준비한다. 3. r' = b mod r를 계산한다. 4. 이 과정을 계속하여 나눈 나머지가 0이 되면 나누는 수는 최대공약수이다. ex) 60과 24 : 60 mod 24 = 12 24 mod 12 = 0 따라서 60과 24의 최대공약수는 12 이 유클리드 호제법을 이번 프로그램에서 어디에 쓸는지 알아보도록 하죠. 눈치 빠르신 분들을 벌써 알아차리셨을지도 모르지만 서로소를 구하는 것이 들어갑니다. 수학에서 서로소는 : 정의 : 두 수의 최대공약수가 1일 때 그 수는 서로소이다 입니다. 따라서 유클리드 호제법으로 최대공약수를 구한뒤 --> 그 최대공약수가 1이면 그 두 수는 서로소 이런 식이 되는 것이죠. 준비는 다 끝났습니다. 그럼 코딩으로 넘어가 보죠. 일단 RSA암호를 시작하기 전에 최대공약수를 구하는 함수를 먼저 만들어 놓도록 하겠습니다. #최대공약수 구하는 거 def gcd(num1, num2): while num2 != 0: num1, num2 = num2, num1%num2 return num1 num2가 0이 아닐때 num1 = num2이고 num2 = num1 mod num2가 되고, 이 과정을 계속하다가 num2가 0이 되는 시점, 즉 num1 mod num2가 되는 시점의 num1을 반환하는 함수입니다. 이제 본격적으로 RSA를 구현해 보죠. p = 991 q = 997 n = p * q tot = (p - 1) * (q - 1) 일단 p = 991, q = 997로 정의합니다(위키백과에 따르면 1000보다 작은 가장 큰 두 세자리 소수라네요). 그리고 N과 (p - 1) * (q - 1)도 구해놓습니다. #공개키 def publickey(): global tot e = 2 while e<tot and gcd(e, tot) != 1: e += 1 return e 공개키를 구하는 함수 publickey()를 만듭니다. 위의 설계에서 설명했다싶이 일단 e는 2로 정해놓습니다. e가 1이면 둘다 시작부터 서로소이기 때문에 의미가 없죠. e가 (p - 1) * (q - 1)과 작을때, 그리고 e와 (p - 1) * (q - 1)의 최대공약수가 1이 아닐때, 즉 서로소가 아니면 e의 값을 계속 증가하고, 만약 e와 (p - 1) * (q - 1)가 서로소라면 그 e값을 반환합니다. e < (p - 1) * (q - 1)이고 e와 (p - 1) * (q - 1)이 서로소가 아닐때 --> e의 값 1증가 --> 만약 e와 (p - 1) * (q - 1)이 서로소라면 --> 그때의 e 반환 공개키를 구했으니 개인키도 구해야겠죠. #개인키 def privatekey(): global e global tot d = 1 while (publickey() * d) % tot != 1 or d == publickey(): d += 1 return d 일단 publickey()는 e를 말하고요, 여기서 ed를 (p - 1) * (q - 1)로 나눈 나머지가 1이 아니거나 d가 e이면 d의 값을 1씩 증가시키고, 위의 조건을 만족시키지 않는, 즉 ed를 (p - 1) * (q - 1)로 나눈 나머지가 1이거나 d가 e가 아닌 수일때 그때의 d값을 반환합니다. ori = int((input("평서문 : "))) eori = ((ori**publickey())%n) print("암호문 : {}".format(eori)) print("N : {}".format(n)) print("공개키 : {}".format(publickey())) print("개인키 : {}".format(privatekey())) input() 마지막으로 평서문을 입력받고, 암호문은 평서문^e mod N임을 이용해 구한뒤, 암호문, N, 공개키, 개인키를 출력합니다. 일단 암호화를 하였으니 복호화도 해야겠죠? 이제 복호화를 한번 해보겠습니다. 복호화는 암호화보다는 조금더 간단한데요 : n = int(input("N의 값을 입력하세요 : ")) eori = int(input("암호문을 입력하세요 : ")) d = int(input("개인키를 입력하세요 : ")) ori = (eori**d)%n print("평서문 : {}".format(ori)) input() 일단 N의 값과 암호문, 그리고 개인키를 입력받고 평서문 = 암호문^d mod N임을 이용해서 평서문을 출력합니다. 간단하죠? 그럼 한 번 실행시켜 보겠습니다. 평서문 : 703050 암호문 : 691282 N : 988027 공개키 : 7 개인키 : 140863 일단 평서문 703050을 입력하였는데요. 암호문, N, 공개키, 그리고 개인키까지 출력이 되는 것을 확인할 수 있습니다. 그럼 한번 복호화를 해보죠. N의 값을 입력하세요 : 988027 암호문을 입력하세요 : 691282 개인키를 입력하세요 : 140863 평서문 : 703050 N, 암호문, 개인키를 입력하니 원래 평서문 703050이 나온것을 확인할 수 있습니다. 이것을 조금 변형하여 문장이나 글자도 암호화할 수 있는데요. ord()함수와 chr()함수를 이용합니다. ord()함수는 그 문자의 아스키값을, chr()함수는 그 숫자의 대응되는 문자(아스키)를 출력하는 함수입니다. 그럼 문장이나 단어를 입력받으면 그 각 문자에 대응되는 숫자가 입력될 것이고 그것을 암호화하면 되는 것이죠. 그러면 : p = 13 q = 29 n = p * q tot = (p - 1) * (q - 1) #최대공약수 구하는 거 def gcd(num1, num2): while num2 != 0: num1, num2 = num2, num1%num2 return num1 #공개키 def publickey(): global tot e = 2 while e<tot and gcd(e, tot) != 1: e += 1 return e #개인키 def privatekey(): global e global tot d = 1 while (publickey() * d) % tot != 1 or d == publickey(): d += 1 return d ori = (input("평서문 : ")) oris = list(ori) orior = [] eori = [] etext = "" for orisc in range(0, len(oris)): orior.append(ord(oris[orisc])) for oriorc in range(0, len(orior)): eori.append(((orior[oriorc]**publickey())%n)) for eoric in range(0, len(eori)): etext += (chr(eori[eoric])) print("암호문(NUMBER) : {}".format(eori)) print("암호문(ASCII) : {}".format(etext)) print("N : {}".format(n)) print("공개키 : {}".format(publickey())) print("개인키 : {}".format(privatekey())) input() 이런식으로 암호화 프로그램을 구성할 수 있겠네요. 복호화도 마찬가지로 n = int(input("N의 값을 입력하세요 : ")) eori = (input("암호문을 입력하세요 : ")) d = int(input("개인키를 입력하세요 : ")) eoris = list(eori) eroiso = [] eroisor = [] eroar = [] text = "" for eorisc in range(0, len(eoris)): eroiso.append(ord(eoris[eorisc])) for eroisoc in range(0, len(eroiso)): eroisor.append((eroiso[eroisoc]**d)%n) for eroisorc in range(0, len(eroisor)): eroar.append(chr(eroisor[eroisorc])) for eroarc in range(0, len(eroar)): text += eroar[eroarc] print("평서문 : {}".format(text)) input() 변수 이름이 길어져서 오타가 생겼네요. 뭐 그냥 그런대로 코딩해야죠(원래 eoriso라고 적어야 하는데 eroiso라고 적음). 실행시켜보면 : 평서문 : today is saturday 암호문(NUMBER) : [116, 297, 354, 327, 283, 301, 131, 202, 301, 202, 327, 116, 117, 316, 354, 327, 283] 암호문(ASCII) : tĩŢŇěĭÊĭÊŇtuļŢŇě N : 377 공개키 : 5 개인키 : 269 평서문 today is saturday를 암호화한것은 tĩŢŇěĭÊĭÊŇtuļŢŇě문자가 나오게 됩니다. 이를 다시 복호화 해보면 : N의 값을 입력하세요 : 377 암호문을 입력하세요 : tĩŢŇěĭÊĭÊŇtuļŢŇě 개인키를 입력하세요 : 269 평서문 : today is saturday today is saturday가 출력되는 것을 알 수 있죠. 이렇게 이번 포스팅에서는 RSA암호를 한번 파이썬으로 구성해보았는데요. 이번에 처음 소스코드 블랙테마를 사용했는데 어떤가요? 어쨋든 이번 포스팅은 여기서 마쳐야 할 것 같은데요. 소스코드는 바로 밑에 넣어놓도록 하겠습니다. 이상, locha였습니다. 요약 : 1. 큰 수는 두 소수의 곱으로 소인수분해 하기 여럽다 p = 991 q = 997 n = p * q tot = (p - 1) * (q - 1) #최대공약수 구하는 거 def gcd(num1, num2): while num2 != 0: num1, num2 = num2, num1%num2 return num1 #공개키 def publickey(): global tot e = 2 while e<tot and gcd(e, tot) != 1: e += 1 return e #개인키 def privatekey(): global e global tot d = 1 while (publickey() * d) % tot != 1 or d == publickey(): d += 1 return d ori = int((input("평서문 : "))) eori = ((ori**publickey())%n) print("암호문 : {}".format(eori)) print("N : {}".format(n)) print("공개키 : {}".format(publickey())) print("개인키 : {}".format(privatekey())) input() n = int(input("N의 값을 입력하세요 : ")) eori = int(input("암호문을 입력하세요 : ")) d = int(input("개인키를 입력하세요 : ")) ori = (eori**d)%n print("평서문 : {}".format(ori)) input() p = 13 q = 29 n = p * q tot = (p - 1) * (q - 1) #최대공약수 구하는 거 def gcd(num1, num2): while num2 != 0: num1, num2 = num2, num1%num2 return num1 #공개키 def publickey(): global tot e = 2 while e<tot and gcd(e, tot) != 1: e += 1 return e #개인키 def privatekey(): global e global tot d = 1 while (publickey() * d) % tot != 1 or d == publickey(): d += 1 return d ori = (input("평서문 : ")) oris = list(ori) orior = [] eori = [] etext = "" for orisc in range(0, len(oris)): orior.append(ord(oris[orisc])) for oriorc in range(0, len(orior)): eori.append(((orior[oriorc]**publickey())%n)) for eoric in range(0, len(eori)): etext += (chr(eori[eoric])) print("암호문(NUMBER) : {}".format(eori)) print("암호문(ASCII) : {}".format(etext)) print("N : {}".format(n)) print("공개키 : {}".format(publickey())) print("개인키 : {}".format(privatekey())) input() n = int(input("N의 값을 입력하세요 : ")) eori = (input("암호문을 입력하세요 : ")) d = int(input("개인키를 입력하세요 : ")) eoris = list(eori) eroiso = [] eroisor = [] eroar = [] text = "" for eorisc in range(0, len(eoris)): eroiso.append(ord(eoris[eorisc])) for eroisoc in range(0, len(eroiso)): eroisor.append((eroiso[eroisoc]**d)%n) for eroisorc in range(0, len(eroisor)): eroar.append(chr(eroisor[eroisorc])) for eroarc in range(0, len(eroar)): text += eroar[eroarc] print("평서문 : {}".format(text)) input() |