준동형 비밀번호 좋아요.

이 보도는?

Python에 같은 종류의 암호 중 하나인 RSA 암호를 설치하여 같은 종류의 암호를 정확하게 사용합니다.이른바 준동형 암호란 암호화 상태에서 계산된 결과가 명문 계산 결과로 직접 변한 불가사의한 성격의 암호를 가리킨다!

RSA 암호

RSA 비밀번호는 1977년 당시 MIT의 리베스트, Shamir, Adleman이 디자인한 첫 공개 키 비밀번호다.이것은 제품에 광범위하게 보급되고 사용되는 공개 키 암호화 방식이며, 준동형성을 가지고 있다.
알고리즘을 실제로 보세요.공개 키 암호화 알고리즘은 세 단계로 나누어 설명한다.키 생성 단계, 공공 키, 개인 키 및 기타 파라미터를 미리 설정하는 데 사용되며, 공공 키로 암호화하는 암호화 단계, 그리고 개인 키로 복호화하는 복호화 단계에 사용됩니다.RSA 암호를 설명하는 알고리즘
또한 명문은 암호화되지 않은 원시 값을 가리킨다.

키 생성 단계

선택 소수 p와 q.

n=pq와 s=lcm(p-1,q-1)을 계산한다.

s와 서로 소박하고 s보다 작은 수 e를 선택하세요.

계산 d=(\rac{1} {e}\mod\s).

비밀 키를 공개 키 e, n으로 설정합니다.

암호화 단계

계산 c=m^e\mod\n, 출력 c.

복호화 단계

계산 m=c^d\mod\n, 출력 m.
RSA 암호 알고리즘이었습니다.간단하기 때문에 안전성에 대한 정의가 엄격하지 않은 부분이 있다.
다음은 실제 실시와 동시에 준동형성을 확실히 가지고 있음을 살펴본다!

Note
\racc {1}은mod\s의 값이기 때문에 단순한 역수가 아니라 역원입니다.

시치미 떼다

우선 키 생성 단계를 설치합니다.포함 함수pow는 Python 3입니다.8보다 작으면 pow(x,e,n)에서 x^e mod\n을 계산할 수 있는 기능이 없기 때문에 Pythn3입니다.8 이상의 동작을 구상했다.
간단하게 보기 위해서 소수 p, q는 충분한 값을 미리 선택해야 한다.lcm는 최소 공배수를 계산하는 함수이고, gen_coprime는 서로 소수를 가진 함수[1]이다.다음은 프로그램의 전체다.

from sympy import prime
from math import gcd

def lcm(x,y):
	return (x*y)//gcd(x,y)		

def gen_coprime(x):
	for i in range(2,x):
		if gcd(x,i)==1:return i

def genkey_rsa(p,q):
	n=p*q # n = p * q
	s=lcm(p-1,q-1) # p-1とq-1の最小公倍数s
	e=gen_coprime(s) #　sと互いに素な数e
	d=pow(e,-1,s) # d = e^-1 mod s
	return (n,e),(d,n) # 公開鍵、秘密鍵
	
def encrypt_rsa(pk,m):
	n,e=pk
	return pow(m,e,n) # c = m ^ e mod n
	
def mult_cipher(pk,x,y):#暗号文で掛け算する関数
	n,e=pk
	return (x*y)%n

if __name__=="__main__":
	p,q=prime(10**6),prime(10**6+1)
	plain_text1=200000
	pk,sk=genkey_rsa(p,q)

	while True:
		print("-"*20)
		print("平文１を入力してください:",end="")
		plain_text1=int(input())
		print("平文２を入力してください:",end="")
		plain_text2=int(input())
		print(f"平文１:{plain_text1}")
		print(f"平文２:{plain_text2}")

		cipher_text1=encrypt_rsa(pk,plain_text1)
		cipher_text2=encrypt_rsa(pk,plain_text2)
		cipher_text3=mult_cipher(pk,cipher_text1,cipher_text2)
		print(f"暗号文１:{cipher_text1}")
		print(f"暗号文２:{cipher_text2}")
		print(f"暗号文１×暗号文２:{cipher_text3}")

		plain_text3=decrypt_rsa(sk,cipher_text3)
		print(f"平文１×平文２:{plain_text3}")

바로 시행하죠.이 프로그램main에서 아래 처리print를 반복합니다.

명문의 입력을 받는다.

명문 암호화.

암호화 값을 곱합니다.

디코딩.

스스로 운전해 본 결과는 다음과 같다.

--------------------
平文１を入力してください:120
平文２を入力してください:90
平文１:120
平文２:90
暗号文１:24883200000
暗号文２:5904900000
暗号文１×暗号文２:226025144791521
平文１×平文２:10800
--------------------

암호 상태에서의 계산 결과는 불분명하지만 복호화 후 명문의 적은 확실합니다!

노트 대화Ctrl+c가 종료되었습니다.또한 명문치(pq 이상)를 너무 많이 입력하면 순조롭게 진행할 수 없다.이번에는 압축해야 하기 때문에 사용하지 않았지만 암호문 계산modint처럼 반에 포장하면 사용하기 쉽다.

왜 이러지?

공식을 수정하면서 확인하세요.두 개의 서로 다른 명문 명칭은 m이다1、m_2.
RSA 암호화 시 c=m^e\mod\n 고려
c_1=m_1^e\mod\n ,c_2=m_1^e\mod\n
이렇게 돼서c_1과 c곱하기1\cdot c_2.c_1\cdot c_2 해독 후
Dec(c_1\cdot c_2) = (c_1\cdot c_2)^d = (m_1^e\cdot m_2^e)^d = (m_1\cdot m_2)^{e\cdot d} = (m_1\cdot m_2)^{e\cdot\frac{1}{e}}=m_1\cdot m_2
.이것은 분명히 m이다1과 m2의 적이기 때문에 RSA 암호는 곱셈에 대해 동일한 유형성을 가진 암호라고 할 수 있다.

총결산

이번에는 RSA 비밀번호만 소개했을 뿐 다른 같은 유형의 비밀번호도 많았다.곱셈을 제외하고 덧셈에도 준동형 암호가 존재하거나 두 가지 성질을 가진 완전 준동형 암호가 존재한다.
비밀번호가 너무 재미있어요. 아름다운 분야예요. 꼭 열심히 공부하세요!
각주
실제 실현에서는 보통 서로 소수를 상수로 지정한다.예를 들어 e=3으로 고정된 상황에서 p와 q의 안전소수에 공을 들이면 서로 소가 된다.↩︎