Some work with GGH

Math 302 Cryptography, April 19, 2017
T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

A function to convert a string to a vector in (ℝ^n), and then a function to convert it back.

This is kind of clunky, but it works for our purposes.

stringToVector[m_,n_] :=Module[ {m1,v,len},
m1=ToCharacterCode[m]+100;
len=Ceiling[Length[m1]/n];
v=Partition[m1,len,len,{1,1},{}];
Return[ ToExpression[Map[StringJoin,Map[IntegerString,v,1],1]]]
];
vectorToString[m_] :=FromCharacterCode[ToExpression[StringCases[StringJoin[ Map[IntegerString,m]], Repeated[_,{3}]]]-100];

Convert a string to vector in (ℝ^4) and then convert it back to a string.

v=stringToVector["Wow, those Kryptos problems were sneaky!", 4]

vectorToString[v]

Form a good basis for L ⊂ (ℝ^3)and compute the Hadamard ratio

v1={13,-42,17};
v2={39,-12,3};
v3={20,9,42};
V={v1,v2,v3};
V//MatrixForm
N[Surd[ Abs[Det[V]]/(Norm[v1]*Norm[v2]*Norm[v3]),3]]

Looks good!

Now create U with integer entries and det(U)=±1

u1={ {1,31,-2},{0,1,-12},{0,0,1}};
u2={{1,0,0},{-2,1,0},{7,-5,1}};
u3={{1,0,0},{43,1,0},{-143,71,1}};
U=u2.u1.u3;
U//MatrixForm
Det[U]

Create the bad basis W=U.V and compute its Hadamard ratio

W=U.V
W//MatrixForm
N[Surd[ Abs[Det[W]]/(Norm[W[[1]]]*Norm[W[[2]]]*Norm[W[[3]]]),3]]

Yep, the rows of W are pretty non-orthogonal!

Let’s encrypt using W

m=stringToVector["Wow, those Kryptos problems were sneaky!", 3];
v=m.W;
r=RandomInteger[{-7,7},3];
e = v+r

We can decrypt using Babai’s algorithm

t=e.Inverse[V];
a=Round[t];
v=a.V;
v1=v.Inverse[W];
vectorToString[v1]