**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.

This application restricts the message length to 128 or fewer characters (bytes). That is because my key generating algorithm yields a prime modulus, n, that is 129 bytes in length, where at first, the highest order byte is explicitly set to one, and the remaining bytes are chosen based on the user’s password. The BigInteger represented by these bytes is then increased until it is found to be prime by the Miller-Rabin primality test. This guarantees that n is at least (a one with about 300 zeros after it), but it is very probably less than . Thus, a message that is more than 128 characters might encode to a number that is larger than the modulus n, and would be corrupted by the encryption process.

Further complicating the matter, once encrypted, the message can sometimes become mapped to a number that, though still less than the the modulus n, is large enough to require 129 bytes, or characters to represent. And so I decided on a simple, but inelegant rule for the application: messages no larger than 128 characters may be encrypted, but messages no larger than 129 characters may be decrypted. This is not a great solution because it can admit messages larger than the modulus for decryption.

It is computationally expensive to generate primes that are much larger than 128 bytes in length (by methods known to me, at least..). I wondered for a while about how to encrypt/decrypt larger messages but could only come up with ideas that involved introducing padding to the message. But as this strategy would seem to introduce vulnerabilities, and having been eager to move on to my next project, I gave up on pursuing the matter.

Of course, once the project was out of mind, and well behind me, I had the idea that messages larger than the modulus, n, could be expressed as polynomials in base n via the division algorithm (just as numbers can be expressed in base 2 for binary, or base 16 for hexadecimal), then the coefficients of this polynomial could be encrypted, and then the polynomial with encrypted coefficients can be evaluated to yield the encrypted message that is larger than the modulus, n. This process could clearly be inverted in order to decrypt and recover the original message. While I’m pretty confident in this idea, I can’t guarantee that it will work without having implemented it, and I’m more interested in moving along with my upcoming project.