A computer science problem by Rocco Dalto

Computer Science Level pending

Let M 1 , M 2 , M 3 , M 4 M_{1}, \: M_{2}, \: M_{3}, \: M_{4} be four plain text messages and ( 1 < = k < = 4 ) (1 <= k <= 4) , where k k is an integer.

If each plain text message M k M_{k} was first enciphered using the affine transformation 5 P + 3 C m o d 26 5 * P + 3 \equiv C \bmod 26 , then was enciphered again using the hill cipher A X j B j m o d 26 A * X_{j} \equiv B_{j} \mod 26 , where matrix A = [ 4 7 10 3 19 1 1 11 2 ] m o d 26 A = \begin{bmatrix}{4} && {7} && {10} \\ {3} && {19} && {1} \\ {1} && {11} && {2}\end{bmatrix} \bmod{26} , decipher the four enciphered messages below and determine which one refers explicitly to the weather.

(1): M S F R O H S I L B H T H Q Y O S P X A L J F O V M C MSFROHSILBHTHQYOSPXALJFOVMC

(2): Z X E P O F R J B D X M Z I Q R C Q T W V V M C X A L ZXEPOFRJBDXMZIQRCQTWVVMCXAL

(3): Z X I P O D Z C L U D Z F R M S G V P U L V M A X A H ZXIPODZCLUDZFRMSGVPULVMAXAH

(4) E Z Q T Z I E Z Q F U D I R Y V Z T S G Z W M L X A L EZQTZIEZQFUDIRYVZTSGZWMLXAL

You can write a general program(in any language) to decipher a cipher of the above type.

The program should not contain any predefined functions or procedures. That is you must create all functions and procedures and they should appear in the program, and not called from a library you created.

3 2 1 4

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Rocco Dalto
Mar 24, 2017

I wrote this program in Free Pascal.

program todecipher; {self contained for brillant}

const maxnum = 30;

type matrix = array[1 .. maxnum,1 .. maxnum + 1] of longint;

 solution = array[1 .. maxnum,1 .. maxnum + 1] of LONGINT;

 realmatrix = array[1 .. maxnum,1 .. maxnum] of real;

 NUMARRAY =  ARRAY[1 .. 100] OF INTEGER;

 CHARARRAY = ARRAY[1 .. 100] OF CHAR;

var a,b,p,holdp,holdb,holda,newa:matrix;

a1,b1,v,n,l,bool,r,m:integer;

NUMLINES,NUMBLOCKS,det:INTEGER;

NUMCOLUMNS:INTEGER;

STRSUM,STRTXT:STRING;

{TOBIG:BOOLEAN;     }

X:solution;

Y,C1:numarray;

letter:chararray;

c:realmatrix;

product:real;

NUMCHARS,BLOCKNUM:INTEGER;

myfile:text;

PROCEDURE CONVERT_NUMTOTEXT(NUM:LONGINT; VAR LETTER:CHAR);

BEGIN

CASE NUM OF

0:LETTER:= 'A';

1:LETTER:= 'B';

2:LETTER:= 'C';

3:LETTER:= 'D';

4:LETTER:= 'E';

5:LETTER:= 'F';

6:LETTER:= 'G';

7:LETTER:= 'H';

8:LETTER:= 'I';

9:LETTER:= 'J';

10:LETTER:= 'K';

11:LETTER:= 'L';

12:LETTER:= 'M';

13:LETTER:= 'N';

14:LETTER:= 'O';

15:LETTER:= 'P';

16:LETTER:= 'Q';

17:LETTER:= 'R';

18:LETTER:= 'S';

19:LETTER:= 'T';

20:LETTER:= 'U';

21:LETTER:= 'V';

22:LETTER:= 'W';

23:LETTER:= 'X';

24:LETTER:= 'Y';

25:LETTER:= 'Z';

END;

END;

PROCEDURE CONVERT_TEXTTONUM(LETTER:CHAR; VAR NUM:LONGINT);

BEGIN

CASE UPCASE(LETTER) OF

'A':NUM:= 0;

'B':NUM:= 1;

'C':NUM:= 2;

'D':NUM:= 3;

'E':NUM:= 4;

'F':NUM:= 5;

'G':NUM:= 6;

'H':NUM:= 7;

'I':NUM:= 8;

'J':NUM:= 9;

'K':NUM:= 10;

'L':NUM:= 11;

'M':NUM:= 12;

'N':NUM:= 13;

'O':NUM:= 14;

'P':NUM:= 15;

'Q':NUM:= 16;

'R':NUM:= 17;

'S':NUM:= 18;

'T':NUM:= 19;

'U':NUM:= 20;

'V':NUM:= 21;

'W':NUM:= 22;

'X':NUM:= 23;

'Y':NUM:= 24;

'Z':NUM:= 25;

END;

END;

function prime(p:integer):boolean;

var n:integer;

begin{prime}

     if p = 1 then

        prime:= false

     else

     if p = 2 then

        prime:= true

           else

             begin{else}

         prime:= true;

         n:=2;

     while (n < trunc(sqrt(p)) + 1) do

         begin{loop}

       if p mod n = 0 then

       prime:= false;

           n:= n + 1;

         end;{loop}

             end{else}

 end;{prime}

PROCEDURE GET NUMEQS NUMBLOCKS(VAR NUMEQS,NUMBLOCKS:INTEGER);

VAR K:INTEGER;

BOOL:BOOLEAN;

BEGIN

IF PRIME(NUMCHARS) THEN

BEGIN

NUMEQS:= NUMCHARS;

NUMBLOCKS:= 1;

END

ELSE

BEGIN

FOR K:= 2 TO (NUMCHARS - 1) DO

BEGIN

IF NUMCHARS MOD K = 0 THEN

NUMEQS:= NUMCHARS DIV K;

END;

BOOL:= TRUE;

K:= 1;

WHILE BOOL DO

BEGIN

K:= K + 1;

IF NUMCHARS MOD K = 0 THEN

BEGIN

NUMBLOCKS:= NUMCHARS DIV K; {FOR SMALLEST FACTOR}

BOOL:= FALSE;

END;

END;

END;

END;

function gcf(m,k:LONGINT):LONGINT;

var n,factor,min:longint;

begin{gcf}

if m <= k then

min:= m

else min:= k;

for n:= 1 to min do

begin{loop}

if (k mod n = 0) and (m mod n = 0)

     then

 factor:= n;

end;{loop}

gcf:= factor;

end;{gcf}

PROCEDURE INITDATA;

VAR HOLDSTR:STRING;

 K,J:INTEGER;

BEGIN

writeln('Enter Enciphered Message, leave no blanks');

readln(holdstr);

writeln;

NUMCHARS:= LENGTH(HOLDSTR);

GET NUMEQS NUMBLOCKS(NUMLINES,NUMBLOCKS);

FOR J:= 1 TO NUMBLOCKS DO

BEGIN

FOR K:= 1 TO NUMLINES DO

BEGIN

CONVERT_TEXTTONUM(HOLDSTR[(J - 1) * NUMLINES + K],HOLDP[K,J]);

END;

END;

writeln('Enter A for affine transformation');

readln(a1);

a1:= abs(a1); {safeguard}

writeln('Enter shift B for affine transformation');

readln(b1);

b1:= abs(b1); {safeguard}

writeln('Enter moduli');

readln(m);

while (GCF(A1,M) > 1) do

BEGIN

writeln('Renter A');

readln(a1);

a1:= abs(a1);

END;

END;

PROCEDURE INITDATA1A;

VAR J,K:INTEGER;

BEGIN

FOR J:= 1 TO NUMLINES DO

begin

writeln('Enter row', j,' of Matrix');

FOR K:= 1 TO NUMLINES DO

begin

read(a[j,k]);

end;

writeln;

end;

for k:= 1 to numlines do

begin

for j:= 1 to numlines do

begin

holda[k,j]:= a[k,j];

end;

end;

end;

procedure matrixmult(a,b:matrix; var summat:matrix);

var j,k,s:integer;

   sum:integer;

begin{matrixmult}

for j:= 1 to NUMLINES do

begin{j}

for k:= 1 to 1 do

begin{k}

     sum:= 0;

for s:= 1 to NUMLINES do

begin{s}

     sum:= sum + a[j,s] * b[s,k];

end;{s}

      summat[j,k]:= sum;

end;{k}

end;{j}

end;{matrixmult}

procedure hold(VAR C:REALMATRIX; A:MATRIX);

var k,j:integer;

begin

for k:= 1 to numlines do

begin

for j:= 1 to numlines do

begin

c[k,j]:= a[k,j];

end;

end;

end;

procedure switch2(var c:realmatrix; l,p,n:integer);

var m:integer;

z:real;

begin{switch}

for m:= 1 to n do

begin{m}

   z:= c[l,m];

   c[l,m]:= c[p,m];

   c[p,m]:= z;

end;{m}

end;{switch}

procedure safeguard2(var c:realmatrix; l:integer; var p:integer; n:integer; var v:integer; var product:real);

var m:integer;

begin{safeguard}

v:=0;

if (c[l,l] = 0) then

begin{then}

v:= 1;

m:= l;

while ((m + 1) <= n) and (v = 1) do

begin{loop}

if c[m + 1,l] <> 0 then

begin{then}

        p:= m + 1;

        switch2(c,l,p,n);

        v:= 0;

        PRODUCT:= -1 * PRODUCT;

end;{then}

m:= m + 1;

end;{loop}

end;{then}

end;{safeguard}

procedure operation1(var a:realmatrix; l,n:integer; VAR PRODUCT:REAL);

var k,m:integer;

x:real;

s:realmatrix;

begin{operation1}

for m:= 1 to n do

begin{m}

s[l,m]:= a[l,m]/a[l,l];

end;{m}

PRODUCT:= PRODUCT * (1/A[L,L]);

for m:= 1 to n do

begin{m}

a[l,m]:= s[l,m];

end;{m}

    end;{operation1}

procedure operation2(var a:realmatrix; l,n:integer);

var k,m,q:integer;

x:real;

s:realmatrix;



begin{op2}

for q:= 1 to n do

begin{q}

if q <> l then

begin{then}

x:= -1 * a[q,l];

for m:= 1 to n do

begin{m}

s[q,m]:= x * a[l,m] + a[q,m];

end;{m}

for m:= 1 to n do

begin{m}

a[q,m]:= s[q,m];

end;{m}

end;{then}

end;{q}

end;{op2}

FUNCTION DETERMINANT(a:realmatrix; n:integer; PRODUCT:REAL):integer;

var j,m:integer;

DET,DIAGONAL:REAL;

begin{DETERMINANT}

DIAGONAL:= 1;

FOR j:= 1 TO N DO

BEGIN{LOOP}

DIAGONAL:= DIAGONAL * (a[j,j]);

END;{LOOP}

IF DIAGONAL = 1 THEN

DET:= 1/PRODUCT

ELSE

DET:= 0;

DETERMINANT:= ROUND(DET);

END;{DETERMINANT}

procedure switch(var c:matrix; l,p,n:integer);

var m:integer;

z:longint;

begin{switch}

for m:= 1 to n + 1 do

begin{m}

   z:= c[l,m];

   c[l,m]:= c[p,m];

   c[p,m]:= z;

end;{m}

end;{switch}

procedure safeguard(var c:matrix; l:integer; var p:integer; n:integer; var v:integer);

var j:integer;

begin{safeguard}

v:= 0;

if (c[l,l] mod m = 0) or (gcf(c[l,l],m) <> 1) then

begin{then}

v:= 1;

j:= l;

while ((j + 1) <= n) and (v = 1) do

begin{loop}

if (c[j + 1,l] mod m <> 0) and (gcf(c[j + 1,l],m) = 1) then

begin{then}

        p:= j + 1;

        switch(c,l,p,n);

        v:= 0;

end;{then}

j:= j + 1;

end;{loop}

end;{then}

end;{safeguard}

procedure operation11(var a:matrix; l,n:integer);

var j,k,i,inverse:longint;

s:matrix;


                  {s is each transformed matrix}

begin{op1}

for i:= 0 to m - 1 do

begin

if (a[l,l] * i) mod m = 1 then

begin

inverse:= i;

end;

end;

for j:= 1 to n + 1 do

begin

s[l,j]:= (a[l,j] * inverse) mod m;

if s[l,j] < 0 then

s[l,j]:= m + s[l,j];

end;

for j:= 1 to n + 1 do

begin{j}

a[l,j]:= s[l,j];

end;{j}

for k:= 1 to n do

begin

for j:= 1 to n + 1 do

begin

a[k,j]:= a[k,j] mod m;

if a[k,j] < 0 then

a[k,j]:= m + a[k,j];

end;

end;

end;{op1}

procedure operation21(var a:matrix; l,n:integer);

var q,j,k,x:longint;

s:matrix;

begin{op2}

for q:= 1 to n do

begin{q}

if q <> l then

begin{then}

x:= m - a[q,l];

for j:= 1 to n + 1 do

begin{j}

s[q,j]:= (x * a[l,j] + a[q,j]);

end;{j}

for j:= 1 to n + 1 do

begin{j}

a[q,j]:= s[q,j];

end;{j}

end;{then}

end;{q}

for k:= 1 to n do

begin

for j:= 1 to n + 1 do

begin

a[k,j]:= a[k,j] mod m;

if a[k,j] < 0 then

a[k,j]:= m + a[k,j];

end;

end;

end;{op2}

procedure onesol(var a:matrix; n:integer);

var j,K:integer;

begin

for j:= 1 to n do

begin

X[J,J]:= A[J,N + 1] MOD M;

IF X[J,J] < 0 THEN

BEGIN

X[J,J]:= M + X[J,J];

END;

end;

end;

PROCEDURE DECIPHER;

VAR J,K,T,N,q:INTEGER;

BEGIN

writeln(' Deciphered blocks using Hill cipher');

writeln(' ---------------------------------------------');

writeln;

writeln;

assign(myfile,'doublecipher.txt');

rewrite(myfile);

FOR J:= 1 TO NUMBLOCKS DO

BEGIN

FOR K:= 1 TO NUMLINES DO

BEGIN

A[K,NUMLINES + 1]:= HOLDP[K,J];

END;

for l:= 1 to numlines do

begin{l}

safeguard(a,l,r,numlines,v);

if v = 0 then

begin{then}

operation11(a,l,numlines);

operation21(a,l,numlines);

end;{then}

end;{l}

ONESOL(A,NUMLINES);

for q:= 1 to numlines do

begin

writeln(myfile,x[q,q]); {write to file for affine transformation}

write(x[q,q],' ');

end;

FOR T:= 1 TO NUMLINES DO

BEGIN

FOR N:= 1 TO NUMLINES DO

BEGIN

A[T,N]:= HOLDA[T,N];

END;

END;

writeln;

END;

END;

procedure DECIPHER2;

VAR K,J,INVERSE_A1:INTEGER;

begin

reset(myfile);

for k:= 1 to numchars do

begin

readln(myfile,c1[k]);

end;

FOR K:= 1 TO NUMCHARS DO

BEGIN

FOR J:= -(M - 1) TO M - 1 DO

BEGIN

IF A1 * J MOD M = 1 THEN

BEGIN

INVERSE_A1:= J;

Y[K]:= ((C1[K] - B1) * INVERSE_A1) MOD M;

IF Y[K] < 0 THEN

Y[K]:= M + Y[K];

END;

END;

END;

WRITELN(' DECIPHERED BLOCKS USING AFFINE TRANSFORMATION');

WRITELN(' -----------------------------------------------------------------------------------');

WRITELN;

FOR K:= 1 TO NUMCHARS DO

BEGIN

WRITE(Y[K],' ');

IF K MOD NUMLINES = 0 THEN

WRITELN;

END;

WRITELN;

WRITELN(' DECIPHERED TEXT:');

WRITELN(' -----------------------------');

WRITELN;

FOR K:= 1 TO NUMCHARS DO

BEGIN

CONVERT_NUMTOTEXT(Y[K],LETTER[K]);

WRITE(LETTER[K]);

END;

close(myfile);

end;

begin

INITDATA;

INITDATA1A;

hold(C,A); {testing to see if (m,det(a)) = 1}

PRODUCT:= 1;

for l:= 1 to numlines do

begin{l}

safeguard2(c,l,r,numlines,v,PRODUCT);

if v = 0 then

begin{then}

operation1(c,l,numlines,PRODUCT);

operation2(c,l,numlines);

end;{then}

end;{l}

DET:= DETERMINANT(c,numlines,PRODUCT);

WHILE (gcf(m,abs(det)) <> 1) or (det mod m = 0) DO

BEGIN

writeln(' GCF(M,DET(A)) <> 1.REENTER MATRIX ');

INITDATA1A;

hold(C,A); {testing to see if (m,det(a)) = 1}

PRODUCT:= 1;

for l:= 1 to numlines do

begin{l}

safeguard2(c,l,r,numlines,v,PRODUCT);

if v = 0 then

begin{then}

operation1(c,l,numlines,PRODUCT);

operation2(c,l,numlines);

end;{then}

end;{l}

DET:= DETERMINANT(c,numlines,PRODUCT);

END;

DECIPHER;

decipher2;

readln;

end.

Running the program using (1) M S F R O H S I L B H T H Q Y O S P X A L J F O V M C MSFROHSILBHTHQYOSPXALJFOVMC the deciphered text is:

W H E N Y O U R A L I V E E V E R Y D A Y I S G O O D WHENYOURALIVEEVERYDAYISGOOD

Running the program using (2) Z X E P O F R J B D X M Z I Q R C Q T W V V M C X A L ZXEPOFRJBDXMZIQRCQTWVVMCXAL the deciphered text is:

W E K N O W T O D A Y I S A R E A L L Y G O O D D A Y WEKNOWTODAYISAREALLYGOODDAY

Running the program using (3) Z X I P O D Z C L U D Z F R M S G V P U L V M A X A H ZXIPODZCLUDZFRMSGVPULVMAXAH the deciphered text is:

W E K N O W T O M O R R O W I S N O T A G O O D D A Y WEKNOWTOMORROWISNOTAGOODDAY

Running the program using (4) E Z Q T Z I E Z Q F U D I R Y V Z T S G Z W M L X A L EZQTZIEZQFUDIRYVZTSGZWMLXAL the deciphered text is:

T H E W E A T H E R C A L L S F O R S N O W T O D A Y THEWEATHERCALLSFORSNOWTODAY

\therefore The answer is (4) E Z Q T Z I E Z Q F U D I R Y V Z T S G Z W M L X A L \boxed{EZQTZIEZQFUDIRYVZTSGZWMLXAL}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...