Symbolic computation using Mathematica

Asymmetric cipher using polynomial algebra

Vivian Feig

Torrey Pines High School

Concept

RSA but with polynomials

Public key encryption system based on (what I think is) a "hard" problem of getting polynomials P(x) and Q(x) from their product and A(x), from the Extended Euclidean Algorithm

I think this is hard because if the number of distinct factors in P(x) and Q(x) is very large, it would be necessary to test a large number of combinations in the EEA

Project I created ended up being easy to crack because you don't have to engage the computationally difficult problem

Overview

Represent a message by converting letters and punctuation marks to integers that become the coefficients of the polynomial M(x)

Encode and scramble using the formula  T(x) = A(x)M(x) mod P(x)Q(x)

I thought this would be difficult to solve unless you knew P(x) and Q(x) distinctly

The recipient of the message knows P(x) and Q(x), so can just compute T(x)P(x)modQ(x) to retrieve the original message M(x)

What's the message?

To generate a message, we just use a simple private key cryptography scheme. What I did was match a list of integers from 1 to 59 to all the lower cased letters and upper cased letters in the alphabet, as well as a few key punctuation points.

privatekey[text_]:=M=Take[FoldList[Plus,0,exponent[{num1_,power_}]:=num1*x^power;
Map[exponent,Partition[Riffle[ReplaceAll[StringCases[text,_],rule[string_]:=Apply[Rule,string];
Map[rule,Partition[Riffle[Flatten[List[CharacterRange["a","z"]," ",".",",",":","!","?",";",CharacterRange["A","Z"]]],Table[i,{i,1,59}]],2]]],Table[i,{i,0,-1+Count[ReplaceAll[StringCases[text,_],rule[string_]:=Apply[Rule,string];
Map[rule,Partition[Riffle[Flatten[List[CharacterRange["a","z"]," ",".",",",":","!","?",";",CharacterRange["A","Z"]]],Table[i,{i,1,59}]],2]]],_]}]],2]]],-1][[1]]

privatekey["Mathematica Rules!"]

Functions in Mathematica

PolynomialExtendedGCD

Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Mauris scelerisque erat vel elit. Etiam a purus tincidunt tortor pulvinar laoreet.

This function is new in symbolic computation in Mathematica 6.0, and it is really useful for our purposes. If you plug in two polynomials P(x) and Q(x), this function outputs the two polynomials A(x) and B(x) such that P(x)A(x) + Q(x)B(x) = G(x), where G(x) is the GCD of P(x) and Q(x).  In other words, this is the Euclidean Algorithm, exactly what I needed for my project. Since I am looking at two relatively prime polynomials, we can expect their GCD to be equal to 1, so PolynomialExtendedGCD[P,Q,x] would yield {1,{A,B}}.

◀     |     ▶

Generating two relatively prime polynomials

To generate two relatively prime polynomials, we have to make sure that none of the polynomials' terms factors overlap. To ensure this, if we have two polynomials of n and m degrees, we generate a list of (n+m) distinct integers using Mathematica's RandomSample function.

list = Flatten[List[
RandomSample[Range[1,256],32]]];

listp=Take[list,8];listq = Take[list,-24];

p=(∏_(a=1)^8)(x-listp[[a]]);q=(∏_(a=1)^24)(x-listq[[a]]);

p1 = PolynomialMod[p,257]

q1 = PolynomialMod[q,257]

We have to take these polynomials modulo some prime because the Euclidean Algorithm works on polynomials defined over a finite field, and otherwise the numbers would get too big. 257 is a good prime number for us because it ensures that all the coefficients we are left with are between 0 and 256, which is more than enough to suit our needs, while still not being too large so that the numbers do not get too huge.

Create a public key (pt. 1)

k =p1*q1;

PolynomialExtendedGCD[p1,q1,x,Modulus->257]

A=PolynomialExtendedGCD[p1,q1,x,Modulus->257][[-1]][[1]];

B=PolynomialExtendedGCD[p1,q1,x,Modulus->257][[-1]][[-1]];

The encoded message

Mathematica is able to do the symbolic computation necessary to get the encoded message we send.

SCRAMBLE=PolynomialMod[PolynomialRemainder[A*M,k,x],257]

Retrieve the message and decode

The recipient of this message will presumably know the secret keys, which are the polynomials P(x) and Q(x). I figured that the code would thus be sufficiently hard to crack, since it is difficult to get these polynomials from their published product. I would later find out that my code is problematic because there are other ways to solve it without using this method. Nevertheless, the method works, it just turns out not to be a very good encryption method. 

Luckily, Mathematica has the functions built in to decode the message as previously explained.

PolynomialMod[PolynomialRemainder[p1*SCRAMBLE,q1,x],257]

StringJoin[ReplaceAll[CoefficientList[PolynomialMod[PolynomialRemainder[
PolynomialMod[(∏_(a=1)^8)(x-listp[[a]]),257]*SCRAMBLE,PolynomialMod[(∏_(a=1)^24)(x-listq[[a]]),257],x],257] ,x],decode[nums_]:=Apply[Rule,nums];
Map[decode, Partition[
Riffle[Table[i,{i,1,59}],Flatten[List[CharacterRange["a","z"]," ",".",",",":","!","?",";",CharacterRange["A","Z"]]]],2]]]]

And thus, the original message is retrieved.

Problems: cracking the code

Unfortunately, I think this scheme ultimately fails. In other words, it should not be too difficult to retrieve M(x) from the polynomial T(x).

If public keys P(x)Q(x) and A(x) are relatively prime, can just apply EEA to these two to get original message

Even if they aren't relatively prime, just need to use EEA with a little bit more manipulation

Apply same method used to encode as to decode; do not even need to try to find P(x) and Q(x), which I still believe to be difficult

SCRAMBLE=PolynomialMod[PolynomialRemainder[A*M,k,x],257]

PolynomialExtendedGCD[A, k,x,Modulus->257];

R = PolynomialExtendedGCD[A, k,x,Modulus->257][[-1]][[1]];

S = PolynomialExtendedGCD[A, k,x,Modulus->257][[-1]][[-1]];

PolynomialMod[PolynomialRemainder[SCRAMBLE*R,k,x],257]

As you can see, this is the same polynomial that we got earlier when we used the secret P(x) and Q(x) polynomials to decode the public key.

Conclusion: moving forward

This project gave me some insight on how Mathematica handles symbolic computation

I would like to continue to explore whether or not the problem of getting P(x) and Q(x) from P(x)Q(x) and A(x) really is a "hard" problem. If it is, my next step is to continue looking for some kind of public key cryptography system that utilizes this hard problem to formulate code that cannot be easily cracked.

Special thanks to

Alex Chang

Abby Brown, Torrey Pines High School

Dr. Salvadaor Gutierrez, SUNY Plattsburgh