A computer science problem by Rocco Dalto

Computer Science Level 4

If a plain text message was first enciphered using the affine transformation $3 * P + 5 \equiv C \bmod 26$ , then was enciphered again using the hill cipher $A * X_{j} \equiv B_{j} \mod 26$ , where matrix $A = \begin{bmatrix}{1} && {2} && {3} \\ {4} && {5} && {6} \\ {1} && {11} && {10}\end{bmatrix} \bmod{26}$ , the enciphered message is: $QVRMHYFXPFUGNFX$ .

Decipher the enciphered text above and express the result as a string of integers.

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.

The answer is 19143024819228111118131422.

1 solution

Rocco Dalto
Mar 23, 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;

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;

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;

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;

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;

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;

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;

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;

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;{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;{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;

PROCEDURE DECIPHER;

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

BEGIN

writeln;

writeln(' Deciphered blocks using Hill cipher:');

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}

end;

FOR T:= 1 TO NUMLINES DO

BEGIN

FOR N:= 1 TO NUMLINES DO

BEGIN

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

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;

writeln;

WRITELN(' LIST OF DECIPHERED INTEGERS USING AFFINE TRANSFORMATION:');

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

WRITELN; writeln;

FOR K:= 1 TO NUMCHARS DO

BEGIN

WRITE(Y[K],' ');

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 we obtain:

The blocks deciphered using the hill cipher are:

$10 \: 21 \: 14$

$5 \: 25 \: 3$

$10 \: 19 \: 3$

$12 \: 12 \: 7$

$18 \: 21 \: 19$

The list of integers to be deciphered using the the affine Transformation are:

$10 \: 21 \: 14 \: 5 \: 25 \:3 \:10 \:19 \:3 \:12 \:12 \:7 \:18 \:21 \:19$

Deciphering using the affine transformation we obtain: $\boxed{TODAYITWILLSNOW}$

As a string of integers we have: $\boxed{19143024819228111118131422}$

Deciphering the enciphered text above without using the program.

To decipher the enciphered text, we begin by using the Hill cipher and setting up the augmented matrix:

$\left[ \begin{array}{ccc|ccccc} 1 & 2 & 3 & 16 & 12 & 5 & 5 & 13\\ 4 & 5 & 6 & 21 & 7 & 23 & 20 & 5\\ 1 & 11 & 10 & 17 & 24 & 15 & 6 & 23\\ \ \end{array} \right] \mod{26}$

$22 * Row_{1} + Row_{2}$ and $25 * Row_{1} + Row_{3} \implies$

$\left[ \begin{array}{ccc|ccccc} 1 & 2 & 3 & 16 & 12 & 5 & 5 & 13\\ 0 & 23 & 20 & 9 & 11 & 3 & 0 & 5\\ 0 & 9 & 7 & 1 & 12 & 10 & 1 & 10\\ \ \end{array} \right] \mod{26}$

$17 * Row_{2}$ and $24 * Row_{2} + Row_{1}$ and $17 * Row_{2} + Row_{3} \implies$

$\left[ \begin{array}{ccc|ccccc} 1 & 0 & 25 & 22 & 2 & 7 & 5 & 25\\ 0 & 1 & 2 & 23 & 5 & 25 & 0 & 7\\ 0 & 0 & 15 & 2 & 9 & 19 & 1 & 25\\ \ \end{array} \right] \mod{26}$

$7 * Row_{3}$ and $Row_{3} + Row_{1}$ and $24 * Row_{3} + Row_{2} \implies$

$\left[ \begin{array}{ccc|ccccc} 1 & 0 & 0 & 10 & 5 & 10 & 12 & 18\\ 0 & 1 & 0 & 21 & 25 & 19 & 12 & 21\\ 0 & 0 & 1 & 14 & 3 & 3 & 7 & 19\\ \ \end{array} \right] \mod{26}$

The deciphered blocks using the Hill cipher are:

$10 \: 21 \: 14$

$5 \: 25 \: 3$

$10 \: 19 \: 3$

$12 \: 12 \: 7$

$18 \: 21 \: 19$

The list of integers to be deciphered using the the affine Transformation are:

$10 \: 21 \: 14 \: 5 \: 25 \:3 \:10 \:19 \:3 \:12 \:12 \:7 \:18 \:21 \:19$

For each integer $j$ where $(1 <= j <= 15)$ we use $P_{j} \equiv 9 * (C_{j} - 5) \mod 26$ .

For $C_{1} = 10 \implies P_{1} \equiv 45 \mod 26 \equiv 19 \mod 26$

For $C_{2} = 21 \implies P_{1} \equiv 144 \mod 26 \equiv 14 \mod 26$

For each $C_{j}$ , where $(1 <= j <= 15)$ we obtain:

$P_{j}:$ $19 \: 14 \: 3 \: 0 \: 24 \: 8 \: 19 \: 22 \: 8 \: 11 \: 11 \: 18 \: 13 \: 14 \: 22$ from which we obtain the deciphered message: $\boxed{TODAYITWILLSNOW}$

As a string of integers we have: $\boxed{19143024819228111118131422}$

A computer science problem by Rocco Dalto

The answer is 19143024819228111118131422.

1 solution

0 pending reports