Some work with GGH
Math 302 Advanced Cryptography
April 19, 2019

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.
It converts the characters in the string m to ASCII, adds 100 to each value (to guarantee each character is 3 digits), and splits the result into a vector in (ℤ^n)

stringToVector[m_,n_] :=Module[ {m1,v,len},
m1=ToCharacterCode[m]+100;
len=Ceiling[Length[m1]/n];
m1=PadRight[m1,len*n,100];
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];

Let’s try it out by converting 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]]

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]]

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]

Decrypt the following message

e = {28416577201091924076204460030253800442534824384253189307784017790876882456921485910994613587089549,-24682024270760520185979877316154968694792459437246905292320279891901773163398031564685095880065544,9258594069960181093614199598977774620046939547359252794863163387029857113298975633534395883666266}