Hill's Cipher
/***************************************/
/* Student Name: Thomas Huff */
/* */
/* CMSC 443 Section 0101 */
/* Homework: Cipher #4 */
/* Account: thuff1@gl.umbc.edu */
/***************************************/
>CMSC 443 Spring 95
>This is cipher four. It is created using Hill's Cipher.
>The block size is 3. It includes known plaintext-ciphertext
>to help you. The cipher is worth 35 points and is due no
>later than April 17.
>
>known plaintext-ciphertext:
>
>LET US GO THEN YOU AND I
>WHEN THE EVENING IS SPREAD OUT AGAINST THE SKY
>LIKE A PATIENT ETHERIZED UPON A TABLE
>ZZE*
>
>PXFMYSHAVRLUIUAQLY
>DLMGAVIZLRVYTOYKHTVEARIITGSIVNLMFLWC
>IJHSOMPPABMMGXMALMZHXHXIDBNTTAMPM
>YDM*
>
>Here is the cipher:
>
>PXF MYS HAV FII NJG VKF IVN HLH IHM WVZ XHJ LKZ IXF
>LAV QGI MXM ZVN XVM KVM TLC
>TWZ WLF PWC FVY NAF AVN BRM VOS AVG LEA WVQ XPH
>RKH*
1 1 0
K= 0 1 1
0 0 3
-1
K = 1 25 9
0 1 17
0 0 9
**********************************************************************
let us go through certain half deserted streets the muttering retreats
of restless nights in one night cheap hotels zl
**********************************************************************
Is the zl the arthors initials or did I mess up???
anyway, this would have taken longer that it did (this look be a good
time to direct your attention to the time stamp.) had I not thrown
together a program so here it is:
// Thomas Huff Cipher #4 Due: April 17, 1995
#include
#include
int mod(int x) // alphabetical only !!!
{
while (x > 25)
x = x-26;
return (x);
}
void convert(char a, char b, char c)
{
int aa, bb, cc;
aa = a - 'a';
bb = b - 'a';
cc = c - 'a';
cout << endl;
cout << char(mod((aa*1 + bb*25 + cc*9)) + int('a'));
cout << char(mod((aa*0 + bb*1 + cc*17)) + int('a'));
cout << char(mod((aa*0 + bb*0 + cc*9)) + int('a')) << endl;
cout << endl;
}
main()
{
int counter = 0;
char a, b, c, d; // for three letter groups
while(1){
counter++;
cout << "Enter three letter group in lower case [" << counter << "] > ";
cout << endl;
a = getchar();
b = getchar();
c = getchar();
d = getchar(); // return
convert(a, b, c);
}
}
here's how it works:
Script started on Thu Feb 23 03:03:19 1995
Note: You have signed onto node UMBC8/9
Account: Thomas Huff
Thursday, February 23, 1995 03:03 AM EST
umbc9[1] > run
Enter three letter group in lower case [1] >
pxf
let
Enter three letter group in lower case [2] >
mys
usg
Enter three letter group in lower case [3] >
hav
oth
Enter three letter group in lower case [4] >
fii
rou
Enter three letter group in lower case [5] >
njg
ghc
Enter three letter group in lower case [6] >
vkf
Any question just send me mail. I'm pretty sleepy and done know just
how coherent this will look to you or anybuddy else in the mourning...
P L A N E T
________ ______ __ __
/ / / / \ / |
/ / / / \ / |
/ /_____/ / V |
( thuff1@gl.umbc.edu )
http://umbc8.umbc.edu/~thuff1
____________________________________________________________________________
Dr. Stephens,
I have not seen anything saying you have the third solution to cipher #4 so
I'm turning mine in hoping I am third person.
Raymond Payne
March 20,1995
Solution to Cipher4
Ciphertext:
pxf mys hav fii njg vkf ivn hlh ihm wvz xhj lkz ixf
lav qgi mxm zvn xvm kvm tlc
twz wlf pwc fvy naf avn brm vos avg lea wvq xph
rkh*
Plaintext:
LET US GO THROUGH CERTAIN HALF DESERTED STREETS THE MUTTERING
RETREATS OF RESTLESS NIGHTS IN ONE NIGHT CHEAP HOTEL SZL*
Method of Solving:
Solving the cipher blew my mind. After figuring out how to solve
for the inverse in mod 26 I proceeded to break the known plaintext
into 3 by 3 matrix. After going through a couple and finding that
they were not invertible I resorted to writing some code to do the
job for me. This code read in all the known plaintext and its
coresponding ciphertext. The code them started at the beginning and
broken the known plaintext into 3 by 3 matrix and calculated it's
inverse. Then it multiplied the resulting matrix by the equivalent
ciphertext. This gave me a value for K. Next the code took the
inverse of the resulting K for the solution,K-1. For each 3 by 3
matrix combination, the code printed out the results. I them had to
go through the results and pick out the sensible looking K-1's. One
problem I found looking at the K-1's is that the matrix had to start
on a 3 boundary. Eliminating the K-1's not starting on a 3 boundary,
I noticed that there were 2 that had the same answer of K-1's. I
took the matrix and multiplied by the ciphertext and discovered
that the resulting plaintext was what I expected. I then proceeded
to multiply the rest of the ciphertext matrix through to solve the
ciphertext.
The code is not supplied since it is rough form and is serving as
a bases for project 4.
The K-1 for the solution is :
| 1 0 0 |
| 25 1 0 |
| 9 17 9 |
________________________________________________________________________
Vigenere Cipher
Bill Carter
cs443
Encrypted plain text by a Vinegere Cipher
YPbks$hnktk$gtgzb$yuypc$eevxa$bljcy$Okcso$luxdd$drcmz
pGhjc$nphli$rAdzt$bwk.Cg$hawdo$ksowd$lczmz$skckx$
csigz$ycwfq$lstzb$bzlzj$ggble$acvhd$mlffb$ysl.Ha$pkblr$
olgyy$ogcou$zx,evx$kxsev$cfyst$k,hawd$xygfg$cmf.
Mzpdb$zzjta$q$-$dcfc$pwcse$mbfrr$mkg,dc$ksasg$blutt
thxrc$wlh,qc$epgbr$mayub$bzjzi$ng$-$kxp$xllzd$wgyec$
covzz$mfsk.E$acPbk$vhn,mg$c,aofw$cnrcg$osvi,u$putlh$gaovc
hawmf$grzw.V$coihc$hyqaw$rmfsu$zk,qop$lukmi$hztic$
hhwsz$omzpf$crmgr$xrvxj.$Tnstk$ogrkt$ddhgb$ltbzm$nldcf$
smztb$ewgls$xqsts$bwqdx$lyblu,$lbwrv$washn$ewhsk$seadh$cbbfr.
ypcfL$vxRvk$psAcf$ethl,Z$wzHhj$llzm
I used your Kaiiski program to determined the key length; and verified it
with the index of coincidence program. The key turns out to be of length
seven. Then I used brute force to solve the encrypted message. I split the
cipher into groups of length seven and looked for matching trigrams. I
replacing the trigram 'haw' with the word 'the' , this gave me three
pieces of the key and I went from there to solve for the key be
determining more plain text from the cipher text. Then once the key was
found applied it to the rest of the cipher text to decrypt the meassage.
Key= CMHIPMH:
Decryption of the cipher text
ABISH$OPWAS$SAILI$NGFRO$MTHEC$ITYOF$ARKHA$NGELS$KTOTHESOLO$VETSK$YISLA
$NDS.ON$THESA$MEVES$SELTH$EREWE$REPIL$GRIMS$SAILI$NGTOV$ISITT$HEHOL$YS
HRI$NES.TH$EWIND$WASFA$VORAB$LE,THE$WEATH$ERFAI$R,THES$EASMO$OTH.THEPI
$LGRIM$S$-$SOME$WEREL$YINGD$OWN,SO$MEHAV$INGABITETO$EAT,SO$MESIT$TINGI
$NGROU$PS$-$WER$ETALK$INGTO$EACHO$THER.T$HEBIS$HOP,TO$O,CAME$OUTON$DEC
K,B$EGANT$OPACETHEBR$IDGE.H$EAPPR$OACHE$DTHEB$OW,SAW$AGROU$POFPE$OPLEG
$ATHER$EDTOG$ETHER.$APEAS$ANTWA$SPOIN$TINGO$UTSOM$ETHIN$GINTH$ESEAA$ND
SPE$AKING,$ANDTH$EPEOP$LEWER$ELIST$ENING.FROMT$HETHR$EEHER$MITS,L$EOTO
L$STOY
Plain text without $
ABISHOPWASSAILINGFROMTHECITYOFARKHANGELSKTOTHESOLOVETSKYISLANDS.ON
THESAMEVESSELTHEREWEREPILGRIMSSAILINGTOVISITTHEHOLYSHRINES.THEWINDWASF
AVORABLE,THEWEATHERFAIR,THESEASMOOTH.THEPILGRIMS-SOMEWERELYINGDOWN,SOM
EHAVINGABITETOEAT,SOMESITTINGINGROUPS-WERETALKINGTOEACHOTHER.THEBISHOP
,TOO,CAMEOUTONDECK,BEGANTOPACETHE
BRIDGE.HEAPPROACHEDTHEBOW,SAWAGROUPOFPEOPLEGATHEREDTOGETHER.A
PEASANTWASPOINTINGOUTSOMETHINGINTHESEAANDSPEAKING,ANDTHEPEOPLEWERE
LISTENING.FROMTHETHREEHERMITS,LEOTOLSTOY
____________________________________________________________________________
RSA Cipher
Brian McEntire
December 6, 1995
Cipher 5B revised
The block size is 3 characters.
n = 1000036000099
e = 100043
287702441275
31507106801
969624057347
373293016481
812808109465
565131842954
410670905445
154747190615
781636169783
992594975652
810311886908
526278204995
114846829421
Cipher 5B revised in deciphered form looks like:
The eagle soars in the summit of heaven
Explanation of method to break this cipher:
This cipher was simple but required writing many small programs to speed
decryption. First, I factored n, and found fi(n) by multiplying (p-1) * (q-1),
p and q being the two prime factors of n --1000033 * 1000003.
I found fi(n) to be 1000034000064.
Then, I programmed the extended Euclidean algorithm for finding
inverses in a mod system in C++. Once I found the inverse to e mod fi(n), I
hard-coded those values into a program I wrote in C++ named rsa.break.cc.
That program took as input a text file of the ciphertext numbers (re-directed
from stdin). Its output is the numbers representing the plain text:
84104101
0 3210197
103108101
32115111
97114115
32105110
32116104
10132115
117109109
10511632
11110232
10410197
118101110
0
The 0's appeared to be extraneous (some storage problem or programming problem)
but they didn't affect the output, which when translated into ASCII was indeed
readable english. To perform this translation, I separated the decrypted
numbers into ascii values by inserting spaces where necessary. I obtained:
84 104 101
32 101 97
103 108 101
32 115 111
97 114 115
32 105 110
32 116 104
101 32 115
117 109 109
105 116 32
111 102 32
104 101 97
118 101 110
Note, I disregaurded the two extraneous zero's. Finally, I wrote a small C
program named trans.c to read each number string from stdin or redirected from
a file, and output its ASCII equivalent. The result was the plaintext:
T h e
e a
g l e
s o
a r s
i n
t h
e s
u m m
i t
o f
h e a
v e n
All of the above mentioned programs follow. They could be generalized to
help other students, but I made them specific to this problem for time's sake.
The programs are fairly straight forward and have few comments.
--------------------------------------------------------------------------
// File inv.cc
// Dec 6, 1995
// Brian McEntire for CSMC 443
#include
#include
int main(void){
Integer n, n0, b, b0, t, t0, q, r, temp;
char num[14]="1000034000064";
n0 = n = atoI(num,10); // modulus -- fi(n)
b0 = b = 100043; // number to compute inverse of
t0 =0;
t =1;
q = n0/b0;
r = n0 - q * b0;
while (r > 0){
temp = t0 - q * t;
if (temp >= 0)
temp = temp % n;
else
temp = n - ((0-temp) % n);
t0 =t;
t = temp;
n0 = b0;
b0 = r;
q = n0/b0;
r = n0 - q * b0;
}
if (b0 != 1)
printf("\nb has no inverse mod n!\n");
else
printf("\n%s\n",Itoa(t % n,10,0));
}
--------------------------------------------------------------------------
// File rsa.break.cc
// Dec 6, 1995
// Brian McEntire for CSMC 443
#include
#include
#define MAXDIGITS 12
int main(void){
int ch;
char c[MAXDIGITS+1]; // digits plus '\0' to hold the num string
int i;
Integer cblock,c1,c2;
// these values for the easy cipher
// Integer e=1019,n=1022117;
// these values are for the hard cipher
Integer e=100043,n;
char n_as_str[14]="1000036000099";
// d is the inverse of e mod n
Integer d;
char d_str[13] = "368414112995";
d = atoI(d_str,10);
n = atoI(n_as_str,10);
do {
for (i=0;i<=MAXDIGITS;i++){
c[i] = '\0';}
do {
ch = getchar();
if (ch == '\n')
printf("\n");
} while ((ch == ' ') || (ch == '\n'));
i =0;
while ((ch != ' ') && (ch != '\n') && (ch != EOF)){
c[i++]=ch;
ch = getchar();
}
cblock = atoI(c,10);
c1 = cblock;
// compute c2 = c1 to the e mod n
c2 = 1;
for (i=38;i>=0;i--){ // 39 bits to store the exponent, e
c2 = c2*c2 % n;
if ((testbit(d,i))==1)
c2 = c2*c1 % n;
}
printf("%s",Itoa(c2,10,0));
if (ch != EOF)
printf("%c",ch);
} while (ch != EOF);
}
--------------------------------------------------------------------------
// File translate.cc
// Dec 6, 1995
// Brian McEntire for CSMC 443
// translate an ASCII file of numbers to acsii characters
#include
#include
int main(void){
int ch,i,letter;
char num[4];
do {
for (i=0;i<4;i++){
num[i] = '\0';
}
do{
ch = getchar();
}
while ((ch == ' ') || (ch == '\n') || (ch == EOF));
i = 0;
while ((ch != ' ') && (ch != '\n') && (ch != EOF)){
num[i] = ch;
ch = getchar();
i++;
}
letter = atoi(num);
printf("%c",letter);
if (ch != EOF)
printf("%c",ch);
} while (ch != EOF);
}
______________________________________________________________________
Mark W. Stirling
Solution to cipher 5b
cipher text
----------------------------------
The block size is 3 characters.
n = 1000036000099
e = 100043
287702441275
31507106801
969624057347
373293016481
278767423296
716145094377
293598311459
430533233021
837192131393
333049585290
154125846106
765532039530
460861360259
263539123130
here is a revised version
287702441275
31507106801
969624057347
373293016481
812808109465
565131842954
410670905445
154747190615
781636169783
992594975652
810311886908
526278204995
114846829421
plain text (output from program)
----------------------------------
Modulus is...................... 1000036000099
First prime factor is........... 1000003
Second prime factor is.......... 1000033
Inverse of 100043 is............ 368414112995
First cipher....
287702441275 -> 84104101
31507106801 -> 3210197
969624057347 -> 103108101
373293016481 -> 32115111
278767423296 -> 9711432
716145094377 -> 11532105
293598311459 -> 11032116
430533233021 -> 10410132
837192131393 -> 115117109
333049585290 -> 109105116
154125846106 -> 32111102
765532039530 -> 32104101
460861360259 -> 97118101
263539123130 -> 110
Second cipher....
287702441275 -> 84104101
31507106801 -> 3210197
969624057347 -> 103108101
373293016481 -> 32115111
812808109465 -> 97114115
565131842954 -> 32105110
410670905445 -> 32116104
154747190615 -> 10132115
781636169783 -> 117109109
992594975652 -> 10511632
810311886908 -> 11110232
526278204995 -> 10410197
114846829421 -> 118101110
I solved this problem by first issuing the factor command on 'e'.
After solving for p and q, I used the Euclidean algorithm to calculate the
inverse of e. I then determined all the correct values by using the Square and
Multiply algorithm for solving mod equations with large values. Here is the
program I used to solve the cipher.....
Dr. Stephens
I am pretty sure that this is the correct answer to cipher 5b. Could
you please let me know if this is correct or not before you grade it. There is
no way to determine if my answers are correct.
-Mark
#include
#include
#include "Integer.h"
Integer SquareAndMultiply(const Integer& value, const Integer& power,
const Integer& modValue);
Integer EuclideanAlgorithm(const Integer& value, const Integer& modValue);
void main()
{
//The factor values were found by using the unix command 'factor'.
const Integer factor1(1000003), factor2(1000033);
const Integer modValue = factor1 * factor2;
const Integer p = factor1 - 1, q = factor2 - 1;
const Integer e = 100043;
Integer e_inverse = EuclideanAlgorithm(e, p * q);
cout << "Modulus is...................... " << modValue << endl;
cout << "First prime factor is........... " << factor1 << endl;
cout << "Second prime factor is.......... " << factor2 << endl;
cout << "Inverse of " << e << " is............ " << e_inverse
<< endl;
ifstream stream;
stream.open("cipher5b.input");
char buffer[512];
cout << "First cipher....\n";
Integer value = 1;
while (value != -2)
{
stream.getline(buffer, 512);
value = atoI(buffer);
if (value > 0)
{
cout << value << " ->\t";
cout << SquareAndMultiply(value, e_inverse, modValue)
<< endl;
}
else if (value != -2) cout << "\nSecond cipher....\n";
}
// cout << SquareAndMultiply(9726, 3533, 11413) << endl;
}
Integer EuclideanAlgorithm(const Integer& value, const Integer& modValue)
{
Integer n0 = modValue;
Integer b0 = value;
Integer t = 1;
Integer t0 = 0;
Integer q = n0 / b0;
Integer r = n0 - (q * b0);
while (r > 0)
{
Integer temp = t0 - (q * t);
if (temp >= 0)
{
temp %= modValue;
}
else temp = modValue - ((-temp) % modValue);
t0 = t;
t = temp;
n0 = b0;
b0 = r;
q = n0 / b0;
r = n0 - (q * b0);
}
if (b0 != 1) return 0;
return t % modValue;
}
Integer SquareAndMultiply(const Integer& value, const Integer& power,
const Integer& modValue)
{
Integer z = 1, dest;
unsigned int l = 3 * sizeof(char) * BITSPERBYTE;
do {
pow(2, --l, dest);
}
while ((power & dest) == Integer(00));
for (unsigned int i = ++l; i > 0; i--)
{
z = (z * z) % modValue;
pow(2, i - 1, dest);
if ((power & dest) == dest)
{
z = (z * value) % modValue;
}
}
return z;
}
______________________________________________________________________
The solution is:
>From the beginning the Mafia has indeed always set itself up as a state
within a State.
My method:
Awful! I tried many a different method, starting with some C programs,
then attempting to use the Integer class you gave us (but the program was
taking along the lines of 30 minutes to calculate exponents). I finally
learned how to use Maple, and figured out exponents by breaking down the
calculation into a procedure.
Anyway, I used unix's factor command to get p and q, and then find phi.
After finding phi, I calculated phi(phi(n)) by using factor on phi(n) and
carrying out the math. To find d, I used the method where:
d = e inverse = e ^(phi(phi(n)) - 1) mod phi(n);
Again, I had to break down the exponent to be able to calculate it. This
gave me d as being 12558433.
In Maple, I defined the following procedure:
go:= proc(x) (x ^ 433 mod n) * ((x ^ 558 mod n) * (x ^ 12) mod n) ^ 1000
mod n; end;
Finding the plaintext was then a matter of passing it as an argument to
this procedure.
______________________________________________________________________
knapsack
The plain text is:
Robert Bly
Poem in three Parts
Oh, on an early morning I think I shall live forever!
I am wrapped in my joyful flesh,
and the grass is wrapped in its cloud of green.
Rising from a bed where I dreamt
Of long rides past castles and hot coals,
The sun lies happily on my knees;
I have suffered and survived the night,
Bathed in dark water, like any blade of grass.
The strong leaves of the box elder tree,
Plunging in the wind, call us to disappear
Into the wilds of the universe,
Where we shall sit at the foot of a plant,
And live forever, like the dust.
Method: my strategy was to figure out the easy vector. I first noticed
that the multiplier had to be 101. It evenly divided the first nine
numbers in the hard vector. I checked the remainder of the last 7 numbers
in the hard vector. It turned out that I could obtain each succeeding
remainder by multiplying the remainder of number 10 mod 101. Thus, the
remainders were 59,76,51,1,61,21,42. The last six were obtained by
multiplying the first by 3,6,12,25,50 and 100 in succession. Then I
picked 2*663 (number 9) as the easy vector number 10, which gave 86802
as the mod for the easy vector. Next I got the rest of the easy vector
numbers. Then I took the inverse mod 86802 of 101 and got 10325. I wrote
a program which read in all the cipher numbers, took their inverse and
then performed the snap algorithm on them.
I just finished this a few minutes ago. There was a bug in the code
because a pair of the cipher pairs were too large when multiplied by 10325
to fit into an integer (I wrote it in C). I factored 10325 into 25 and
413 and then did two multiplications which gave the desired results (one
of the big numbers was 'sh' whose cipher 208606*10325 was too large.)
Dave Queen