Encrypted word dictionary with RSA encryption

oneidacharisse (81)
Hello, I'm all over the place. But I wanted to make an encrypted word dictionary with the RSA system. But I have a problem before generating the word encryption, I can't compute the last part! And I would like to display the result of the multiplication without the power how can I do ?

(I found the code to multiply large numbers on github.)

KaratsubaMultiplication.h file
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
/*
 *KaratsubaMultiplication.h
 *
 *Created on: Feb 4, 2015
 *     Author: Evin Ugur (http://evinugur.com)
 */

#
ifndef KARATSUBAMULTIPLICATION_H_
#define KARATSUBAMULTIPLICATION_H_

int getLength(long long value);	// returns the number of digits a number has
long long multiply(long long x, long long y);	// Karatsuba multiplication of two numbers

#
endif /*KARATSUBAMULTIPLICATION_H_ */


main.cpp file 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
 
#include <iostream>
#include <string>
#include <algorithm>
#include <bits/stdc++.h>
#include <stdlib.h>
#include <sstream>
#include <ctime>
#include <vector>
#include <windows.h>
#include <stdio.h>
#include "KaratsubaMultiplication.h"
using namespace std;

int gcd(int a, int h)
{
	int temp;
	while (1)
	{
		temp = a % h;
		if (temp == 0)
			return h;
		a = h;
		h = temp;
	}
}

int getLength(long long value)
{
	int counter = 0;
	while (value != 0)
	{
		counter++;
		value /= 10;
	}

	return counter;
}

long long multiply(long long x, long long y)
{
	int xLength = getLength(x);
	int yLength = getLength(y);

	// the bigger of the two lengths
	int N = (int)(fmax(xLength, yLength));

	// if the max length is small it's faster to just flat out multiply the two nums
	if (N < 10)
		return x * y;

	//max length divided and rounded up
	N = (N / 2) + (N % 2);

	long long multiplier = pow(10, N);

	long long b = x / multiplier;
	long long a = x - (b *multiplier);
	long long d = y / multiplier;
	long long c = y - (d *N);

	long long z0 = multiply(a, c);
	long long z1 = multiply(a + b, c + d);
	long long z2 = multiply(b, d);

	return z0 + ((z1 - z0 - z2) *multiplier) + (z2 *(long long)(pow(10, 2 *N)));

}

//Random number generating function
int random(int from, int to)
{
	return rand() % (to - from + 1) + from;
}
//function to return random prime numbers
double randomprime()
{
	static std::vector<double> primenumber;
	int num, i, count;

	int n = 50000;
	for (num = 1; num <= n; num++)
	{
		count = 0;
		for (i = 2; i <= num / 2; i++)
		{
			if (num % i == 0)
			{
				count++;
				break;
			}
		}

		if (count == 0 && num != 1)

			primenumber.push_back(num);
	}

	int upto = primenumber.size();

	// When you get here, the dictionary file has been read into the words vector.
	int randomline = random(2, upto);	// pick a random number 2 - dictionary size
	return primenumber[randomline];	// return that word from the dictionary
}
//In order to calculate pow(a,b) % n to be used for RSA decryption, 
//the best algorithm I came across is Primality Testing 1) which is as follows:
int modulo(int a, int b, int n)
{
	long long x = 1, y = a;
	while (b > 0)
	{
		if (b % 2 == 1)
		{
			x = (x *y) % n;	// multiplying with base
		}

		y = (y *y) % n;	// squaring the base
		b /= 2;
	}

	return x % n;
}

int main()
{
	srand(time(0));
	double count;
	for (int i = 0; i <= 200; i++)
	{
               //2 random prime numbers
		double a = randomprime();
		double b = randomprime();
		double n = multiply(a, b);
		double totient = multiply((a - 1), (b - 1));
		double e = 2;

		//for checking co-prime which satisfies e>1
		while (e < totient)
		{
			count = gcd(e, totient);
			if (count == 1)
				break;
			else
				e++;
		}

                //here is that I can't code, I have to do a division with big numbers, is that the problem?


		//k can be any arbitrary value
		//double k = 2;
                //prod_k_tot = multiply(k, totient);
		//choosing d such that it satisfies d *e = 1 + k *totient
		//d = (1 + prod_k_tot)/e;

		cout << "a = " << a << " b = " << b << " n = " << n << " modulo = " << modulo(a, b, n) << " totient = " << totient << " e = " << e << endl;
	}
}


I have to use the Newton-Raphson method?
Last edited on
helios (17574)
Uh... Huh?

First, if you're using simple long longs then you don't need a multiplication algorithm. The processor already knows how to multiply those numbers!
Second, multiplying two 64-bit numbers gives a 128-bit number. You CANNOT get around this by using double, because after 2^53 double is only able to store even numbers. You need arbitrary precision arithmetic to implement RSA, unless you want pitifully tiny keys that any computer can crack basically instantly. There's no way around it.

FYI, when using RSA the minimum for security nowadays is considered 2048-bit keys (1024-bit keys have been cracked). Your key space is too tiny by a factor of about 10^577.
jonnin (11437)
at some point they really need to sit down and make a new model.
the 'double the key size every few years and fix all the old software that used the previous size' approach is poor.
Ganado (6811)
There already are alternatives to RSA (and non-EC Diffie-Hellman). Elliptic-curve cryptography can be used, although theoretically that could be susceptible to quantum computing attacks. There's other quantum-resistant algorithms as well, but they aren't in wide use as far as I know (and I don't know much about them).

Anyway... it looks like the code OP is using was implemented more for academic purposes and not for actual key exchange capabilities. I hope. I'd just assume you don't have to worry about overflow for purposes of the assignment, but that does make it pretty useless in real life.
Last edited on
oneidacharisse (81)
Hello, I am very aware that this code is not really usable in real life. My wish was to make a theoretical test program. Thank you anyway for pointing this out to me, I don't want to mislead other people. I'm doing this more to learn how to code different things than to crack encryption keys. And as you can see I still have some things to learn! I don't know "arbitrary precision arithmetic" in C++, is it necessary to use it or can I just change the type of variable from double / int to long? Can this kind of modification allow me to do my division which will allow me to encrypt a character afterwards ? Thanks again for all your answers and clarifications.
jonnin (11437)
you need a third party library -- standard c++ does not support extended sized numerical types like 300 byte integers or 256 bit floating point etc. Some hardware has more support on the chip so you can do it in assembly in the c++ up to that limit eg many cpu have a 128 bit int now. This is not useful -- a 128 bit int isnt any better security and its a ton of hassle.

If its just for fun, use unsigned long long (64 bit on modern machines). Avoid doubles, they are not useful in any way I know of here. Keep your keys 32 bit and then if you multiply they will fit.

if the point is to study rsa, carry on.
if the point is to garble data casually to annoy other students or something, just xor with a random number works -- use the seed as the key, 4 or 5 lines and its good enough to keep out anyone with a life.
Last edited on
Ganado (6811)
You don't do division, you do the modular arithmetic multiplicative inverse. Use the Extended Euclidean algorithm.
http://www-math.ucdenver.edu/~wcherowi/courses/m5410/exeucalg.html
"The Extended Euclidean Algorithm for finding the inverse of a number mod n." section.

https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/
Last edited on
oneidacharisse (81)
Hello my goal is to study, I have no other ambition than to learn. And for that, all your answers help me a lot. For the long haul it's that kind of variable that I need: 

1
2
3
4
5
6
7
8
9
 
#include <stdio.h>

int main()
{
    long long l = 9007199254740992;
    double d = (double)l;
    d += 1;
    printf("9007199254740992 + 1 = %lld\n", (long long)d);
}



And for the division, I'm going to study what you indicated I was probably wrong.

Thank you for your answers.
jonnin (11437)
I don't know what you are trying to do with the double, but be aware:
the long long has more digits of precision, the double can represent larger and smaller values due to scientific notation concept, but it has fewer digits. Both are 64 bits, but the long long uses all 64 bits for digits of its number. The double uses a good chunk of those bits for its exponent part. I can never remember the details but I think it has 53 bits of numbers, and 2^64 vs 2^53 is a huge difference in range.

in encryption where the numbers need to be primes, rounding them off will cause various issues (mostly makes it easier to factor the key but there may be other side effects depending on your implementation details). Again, I think using a pair of prime 32 bit ints multiplied into a 64 bit int is the right way to do the encryption part using machine sized data.
Last edited on
Topic archived. No new replies allowed.