**Notes:**

- I have created a simple C# Windows application that encrypts/saves/loads up to 128 characters of text. It is intended to serve as a rudimentary password manager.
- You can view/download the full source on my Github repository.

It seems, these days, that an online livelihood comprises too many disparate services, profiles, and accounts, and far, far too many passwords to all keep straight. Common strategies include passwords that are the names of beloved pets or next of kin, simple alphanumeric sequences, or to use the same password for every account. Of course, these strategies are security no-nos. Secure passwords are complex, hard to guess, and consequently, hard to memorize.

There are many, much better password managers out there, but I thought I’d try to make my own.. I chose to do this project in MSVS C# over, say, Java or Python for some of C#s readymade features, like save and load Windows dialogs, and its generally easy GUI development process. This decision, however, was not without some shortcomings; unlike the Java language BigInteger class, the C# BigInteger class is scant on features. There is no C# BigInteger primality testing method, no inverse mod n method, and there is no method that generates random BigIntegers. These are all necessary components of proper encryption schemes.

Another hurdle to this project was that instead of using a static encryption key, saving the encrypted password or password hash associated with each ciphertext, and verifying that a user has entered a correct password before decrypting, I designed a method to derive a unique encryption key from the user’s password. In this way, it is not necessary to save or store the user’s password or password hash at all. Attempting to decrypt with an incorrect password will (likely) yield a different encryption key, and so, not properly decipher an encrypted text.

While very famous, RSA is an asymmetric encryption scheme, where users have both a public key, and a separate, private key. It is meant to facilitate secure communication among users on a network, and so, it isn’t an appropriate encryption scheme for this project. However, a very similar symmetric encryption scheme, modeled after RSA will suffice. Whereas Euler’s Theorem underpins the RSA encryption scheme, the less general Fermat’s Little Theorem is all that is needed here.

**Fermat’s Little Theorem:**

where p is prime, and

This can be read to say that any whole number that is not zero, and not a multiple of some particular prime, when raised to the power of that particular prime minus one, will always have a remainder of one when divided by that particular prime.

I think that the best way to prove Fermat’s Little Theorem, or to understand why it is true is via the group theoretical perspective. For some whole number, p, whole numbers less than p that have no divisors in common with p form a finite group under the operation of multiplication. If p is a prime number, then no whole number less than p can have any divisors in common with p, and so, such a group must have p-1 elements. Lagrange’s Theorem states that for every finite group, G, the order (the number of elements) of every subgroup of G divides the order of G. Hence if the order of G is p-1, where p is prime, all of the cyclic subgroups generated by the elements of G must have an order that divides p-1.

A couple example tables might help illustrate Fermat’s Little Theorem.

In the first table above, I’ve taken all the numbers in the leftmost column, raised them to the power of the numbers in the top row, and then taken their remainders after dividing by the prime number, 5. In the second table I did the same, but divided by the prime number 7 instead of 5. Each row can be taken to represent the cyclic subgroups generated by the elements of and , respectively. Note that in both tables, the rightmost column has only ones. This result is precisely what is claimed by Fermat’s Little Theorem.

Multiplying both sides of the congruence given in Fermat’s Little theorem by the number, a, gives

This congruence suggests the following encryption scheme:

- Choose any number, e, from the group . i.e. the units of p-1, a group formed by multiplication of whole numbers less than p-1 which have no divisors in common with p-1.
- find d, the inverse of e in .
- encrypt message, a, as where c is the cipher message.
- decrypt cipher message, c, with to recover plaintext message, a.

To explain why this works, begin with e, and its inverse d in . This means that for some whole number, k,

and so,

As stated earlier, the C# BigInteger class is not equipped with an inverse mod n method, so I had to write my own. Solving this problem is equivalent to solving a linear Diophantine equation in two variables: Provided two whole numbers, a and b, find whole numbers, x and y, for which

Subtracting the term, b*y, from both sides of this equation, demonstrates the equivalence of solving the Diophantine equation to finding modular inverses.

Thus, numbers a and x are inverses of one another, mod b.

Why groups, U(n), can only contain elements that are relatively prime to n is illustrated by the equivalence of these two problems. If it were desired to find the inverse of a, mod b, but the greatest common divisor of a and b is not one, the Diophantine equation yields a contradiction; the right-hand side is divisible only by one, whereas the left-hand side is divisible by GCD(a,b).

In such an instance, a has no inverse, mod b, but groups require that all its elements have inverses.

As the Diophantine equation is linear, its general solution will consist of the solution to its homogeneous equation, plus its particular solution.

A solution solution of the homogeneous equation, , is easy to spot:

The particular solution is commonly found using the Extended Euclidean Algorithm. That is to use the regular Euclidean Algorithm to find GCD(a,b), and then work backwards to find an x and y that satisfy the Diophantine equation.

Example:

Find for which .

Thus the Euclidean Algorithm shows (second to last row) that 5344 and 2077 are relatively prime, i.e. GCD(5344, 2077) = 1. Now work backwards to find x and y in terms of 5344, 2077.

Working backwards, as done above, can become a cumbersome and tricky procedure, requiring a sort of recursive back-substitution process, but with intermittent times when it is advantageous to simplify the expression in a strategic fashion. Thankfully, my Number Theory textbook offers an alternative to this “working backwards” procedure that is much more easily codified. The process involves writing the problem as a system of two equations in two unknowns, then producing new equations by adding multiples of those equations together until an equation is produced that is equal to GCD(a,b).

Example:

With the solution to the homogeneous equation from earlier, and now the particular solution, the example problem is solved: ,

Furthermore, with the particular solution, the expression shows that the inverse of 5344 (mod 2077) is 850, and the inverse of 2077 (mod 5344) is 3157.

and

I implemented the procedure used above in a C# method that operates on C# BigIntegers. Provided two BigIntegers, x and y, ExtendedEuclideanAlg returns a three-tuple (i, j, GCD(x,y)), where xi + yj = GCD(x,y). The method works by first initializing two equations that equal abs(x), and abs(y) on the right-hand side, respectively. If x or y are negative, that information is preserved on the left-hand side. This step simplifies the algorithm because the aim can be narrowed to decrease the right-hand side until equaling GCD(x,y). At every iteration of the main loop, a new equation is produced by subtracting the largest multiple the last equation from the second to last equation for which the right-hand side of the equation remains positive. Once the right-hand side is equal to GCD(x,y) the process terminates. I put a little check to also terminate the process accordingly for the case when GCD(x,y) is not one, so that the last entry is always equal to GCD(x,y). Also, I made the method track every step of the problem in lists (u,v,n). While the entirety of the lists are not returned, they are still sometimes desirable, so I left them in. A more efficient method should only require storing two equations at once.

public static BigInteger[] ExtendedEuclideanAlg(BigInteger x, BigInteger y) { List<BigInteger> n = new List<BigInteger>(); List<BigInteger> u = new List<BigInteger>(); List<BigInteger> v = new List<BigInteger>(); BigInteger q, r; //initialize: // [_____u____________v____________n_____] // R0: [ sign(x)*x + 0y = abs(x) ] // R1: [ 0x + sign(y)*y = abs(y) ] n.Add(x * x.Sign); n.Add(y * y.Sign); u.Add(x.Sign); u.Add(0); v.Add(0); v.Add(y.Sign); // add multiples of rows together until n.last == gcd(x,y) while ((!(BigInteger.Equals(n[n.Count - 1], BigInteger.One))) && (!BigInteger.Equals(n[n.Count - 1], n[n.Count - 2]))) { q = BigInteger.DivRem(n[n.Count - 2], n[n.Count - 1], out r); //if n.last divides n.secondToLast, // n.last == gcd(x,y) if (BigInteger.Equals(r, BigInteger.Zero)) { q = q - BigInteger.One; } n.Add(n[n.Count - 2] - q * n[n.Count - 1]); u.Add(u[u.Count - 2] - q * u[u.Count - 1]); v.Add(v[v.Count - 2] - q * v[v.Count - 1]); } // u.last*x + v.last*y = n.last = gcd(x, y) return new BigInteger[3] { u.Last(), v.Last(), n.Last() }; }

The other requirement for this project is the generation of large primes. Although I took an introductory class in Number Theory, I am admittedly not on the level to understand why the Miller-Rabin primality test works. Wikipedia states that its correctness relies on the unproven Extended Riemann Hypothesis. The algorithm offers a probabilistic measure of the likelihood that it will incorrectly decide a composite number is a prime (false-positive). This probability is a function of the number of iterations that the algorithm is allowed to iterate, with that probability stated as at most , k iterations.

Here is the pseudo-code that Wikipedia provides:

write n − 1 as 2r·d with d odd by factoring powers of 2 from n − 1 WitnessLoop: repeat k times: pick a random integer a in the range [2, n − 2] x ← ad mod n if x = 1 or x = n − 1 then continue WitnessLoop repeat r − 1 times: x ← x2 mod n if x = 1 then return composite if x = n − 1 then continue WitnessLoop return composite return probably prime

Note that this procedure relies on the ability to generate random numbers. Since the C# BigInteger class does not provide such a method, it is necessary to write one. I wasn’t very interested in doing so, and was able to quickly find someone else’s solution on stack overflow.

Though I don’t understand the Miller-Rabin primality test, I was able to work through the pseudocode and produce a working implementation in C#:

public static double MillerRabinPrimalityTest(BigInteger n, int numTrials, Random random) { //Probability that n passes test but is not prime ~ 4^(-numTrials) if ((n == 2) || (n == 3) || (n == 5)) { return 1.0; } if (n.IsEven) { return 0.0; } else { //find d, r, for which d*(2^r) = n-1 BigInteger d = n - 1; int r = 0; while (d.IsEven) { r++; d = d / 2; } BigInteger nMinusThree = n - 3; for (int i = 0; i < numTrials; i++) { BigInteger a = RandomBigIntegerLessThan(nMinusThree, random); while (a < 2 || a > nMinusThree) { a = RandomBigIntegerLessThan(nMinusThree, random); } BigInteger x = BigInteger.ModPow(a, d, n); if (!(x.IsOne || (x == (n - 1)))) { int j = 1; while ((j < r) && (x != (n - 1))) { x = BigInteger.ModPow(x, 2, n); if (x.IsOne) { return 0.0; } j++; } if (x != (n - 1)) { return 0.0; } } } return Math.Pow(4.0, Convert.ToDouble(-numTrials)); } }

Finally, I devised of a method to generate (e, d, n) encryption keys from the hashcode of whatever password a user might provide:

public static BigInteger[] PasswordToEDN(string password, int bytewidth) { //derives from password string //numbers e, d, n // for which // ed ~ 1 (mod (n-1)) // and // n > 256^bytewidth // and // n is prime byte[] temp = new byte[bytewidth + 1]; temp[bytewidth] = 1; Random rnd = new Random(); //derive a large prime number, n, from password hashcode BigInteger hashcode = new BigInteger(Math.Abs(password.GetHashCode())); BigInteger modMax = BigInteger.Parse("2147483647"); for (int i = 0; i < bytewidth; i++) { temp[i] = (byte)(hashcode % 256); hashcode = BigInteger.ModPow(hashcode, 2, modMax); } BigInteger n = new BigInteger(temp); n = NextProbablePrime(n, 100, rnd); //find e, the jth number that is //relatively prime to n-1. // GCD(e_j, n-1) == 1 //where j is derived from //the password hashcode BigInteger nMinusOne = n - 1; BigInteger e = new BigInteger(1); int j = (int)(hashcode % 1000); for (int k = 0; k < j; k++) { e = nNextRelativePrimeToM(e, nMinusOne); } //find e inverse, d BigInteger d = xInverseModN(e, nMinusOne); return new BigInteger[] { e, d, n }; }

The same method is used for generating keys (e, d, n) when encrypting and decrypting, but the only the numbers e and n are used to encrypt with modular exponentiation of the message, whereas the numbers d and n are used to decrypt with modular exponentiation. The message itself must encode to a whole number that is less than the prime modulus, n, hence my program’s restriction that the message can not exceed 128 characters. Were the message to encode as a number larger than n, it would be corrupted by the encryption/decryption process. Unfortunately, restricting the message to only as many as 128 characters is not a catch-all solution. My program guarantees that a message with 128 or fewer characters will not encode as a number that exceeds the modulus n, but it can end up mapped, as an encrypted message, that is still less than n, but represents a number that would be a message greater than 128 characters in length. I made my program just refuse to operate should it encounter such a scenario, though I suspect a more elegant solution would be available if I were to introduce some padding into the message. I might revisit the project at some later date and work on it.