제한된 지수 크기로 인해 C#에서 비대칭 키를 만드는 방법은 무엇입니까?

Question

비대칭 키를 사용하여 데이터를 암호화하고 해독하는 작은 소프트웨어를 만들고 있습니다.

문제는 내가 C#으로, 심지어 내가 사용하는 경우 코딩하고있다 :

BigInteger.Pow(BigIntenger myNumber, int myExponent); 

지수는 "INT"이고 내 값은 인터넷 용 큰하는 것입니다.

실수를하지 않고 신속하게 설명하고 확실하게하기 위해 비공개 키를 사용하지 않고도 해독하기가 어렵도록 큰 숫자를 사용해야합니다.

그래서 나는

• N = P * Q
• P가 Q는 모두 소수이다.
• M = (P-1) + (Q-1)
• C가 가
• 그런와 U를 찾을 M
으로 소수 인 : C × U + M × V = 1

공개 키 (N, C).

개인 키 (U, N).

예를 들어 "Bonjour!"를 암호화하고 싶습니다. UTF8로

당신은해야합니다!

B⇔66/o⇔111/n⇔110/j⇔106/o⇔111/u⇔117/r⇔114/(ESPACE) ⇔32/⇔33

valueOfB = (66^C) %의 N :

그러자 C의 전력 모듈로 N.

전 각 숫자를 올린다.

이제 메시지가 암호화됩니다. 당신이 암호를 해독하려면

, 각 지수 U에 의한 값과 모듈로 N을 곱해야

예 : (valueOfB^U) %의 N은

그래서 나는이 작업을 수행 할 수 있습니다 작은 수를 사용하기 때문에 "int"에 맞는 작은 U 값을 가지지 만 안전하지는 않습니다. BigInteger와 int가 아닌 큰 U로 어떻게 할 수 있습니까?

Answer 1

BigInteger.Pow의 BigInteger는 매우 복잡한 숫자입니다.

이진 곱셈은 n- 비트 번호에 m- 비트 수를 (대략적으로 말하면) 곱하면 약 (n+m) 비트 응답을 생성합니다.지수가 승산을 반복하고, 승산은 또한 반복되므로

10 * 4096 = 0b1010 * 0b1_0000_0000_0000 (4 bits, 13 bits) 
40960 = 0b1010_0000_0000_0000 (16 bits) 

16 * 4096 = 0b1_0000 * 0b1_0000_0000_0000 (5 bits, 13 bits) 
65536 = 0b1_0000_0000_0000_0000 (17 bits) 

15 * 4095 = 0b1111 * 0b1111_1111_1111 (4 bits, 12 bits) 
61425 = 0b1110_1111_1111_0001 (16 bits) 

, 우리는 512 비트 숫자의 힘에 1024 비트 수를 올리는 것은 1024 * 512 비트의 영역에서 응답되고 있는지 확인할 수 (524288 비트, 65536 바이트).

그러나 그런 다음 모듈러스 연산을 수행하여 1024 비트 숫자의 영역으로 되돌립니다. 그건 꽤 낭비입니다.

다행히도 효율적으로 수행하기위한 알고리즘이 존재합니다. modular exponentiation. 고맙게도 당신을 위해, .NET은 앞서 나가서 그것을 작성했습니다.

당신이 찾고있는

valueOfB = BigInteger.ModPow(66, U, N);