A computer science problem by Rocco Dalto

Computer Science Level pending

If the plain text message $TODAYITWILLSNOW$ 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}$ , find the enciphered text.

Encipher the message above and express the result as a string of integers.

Write a general program(in any language) to encipher and decipher a cipher of the above type. Check your program by deciphering the enciphered message obtained using the given affine transformation, the given matrix, and the plain text message above.

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 1621171272452315520613523.

1 solution

Rocco Dalto
Mar 24, 2017

I used Free Pascal to write the program.

program doubleCipher;

const maxnum = 30;

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

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

 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;

var NUM,C1,Y:NUMARRAY;

NUMCHARS,M,A1,B1,COUNT:INTEGER;

LETTER:CHARARRAY;

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

v,n,l,bool,r:integer;

NUMLINES,NUMBLOCKS,det:INTEGER;

NUMCOLUMNS:INTEGER;

STRSUM,STRTXT:STRING;

{TOBIG:BOOLEAN;     }

x:SOLUTION;

c:realmatrix;

product:real;

BLOCKNUM:INTEGER;

MYFILE:TEXT;

PROCEDURE CONVERT_NUMTOTEXT(NUM:INTEGER; 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:INTEGER);

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

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;

PROCEDURE INITDATA;

VAR HOLDSTR:STRING;

 K:INTEGER;

BEGIN

writeln('Enter plaintext message, no blanks.');

readln(holdstr);

NUMCHARS:= LENGTH(HOLDSTR);

FOR K:= 1 TO NUMCHARS DO

BEGIN

CONVERT_TEXTTONUM(HOLDSTR[K],NUM[K]);

END;

writeln;

writeln('Enter moduli');

readln(m);

writeln('Enter A');

readln(a1);

a1:= abs(a1); {safeguard}

writeln('Enter shift B');

readln(b1);

b1:= abs(b1); {safeguard}

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

BEGIN

writeln('Renter A');

readln(a1);

a1:= abs(a1);

END;

GET NUMEQS NUMBLOCKS(NUMLINES,NUMBLOCKS);

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

VAR K:INTEGER;

BEGIN

WRITELN(' ENCIPHERED BLOCK(AFFINE TRANSFORMATION:');

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

FOR K:= 1 TO NUMCHARS DO

BEGIN

C1[K]:= (A1 * NUM[K] + B1) MOD M;

WRITE(C1[K],' ');

END;

WRITELN;

writeln;

WRITELN(' ENCIPHERED TEXT(AFFINE TRANSFORMATION:');

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

WRITELN;

FOR K:= 1 TO NUMCHARS DO

BEGIN

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

WRITE(LETTER[K]);

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

VAR J,K:INTEGER;

STRSUM,STRB,STRSUM2,STRP:STRING;

LETTER:CHAR;

BEGIN

FOR J:= 1 TO NUMBLOCKS DO

BEGIN

FOR K:= 1 TO NUMLINES DO

BEGIN

HOLDP[K,J]:= C1[(J - 1) * NUMLINES + K];

END;

writeln; writeln;

STRTXT:= '';

WRITELN(' ENCIPHERED BLOCKS(HILL CIPHER):');

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

FOR J:= 1 TO NUMBLOCKS DO

BEGIN

STRSUM:= '';

FOR K:= 1 TO NUMLINES DO

BEGIN

P[K,1]:= HOLDP[K,J];

END;

MATRIXMULT(A,P,B);

FOR K:= 1 TO NUMLINES DO

BEGIN

B[K,1]:= B[K,1] MOD M;

STR(B[K,1],STRB);

HOLDB[K,J]:= B[K,1];

STRSUM:= STRSUM + STRB + ' ';

CONVERT_NUMTOTEXT(B[K,1],LETTER);

STRTXT:= STRTXT + LETTER;

END;

WRITELN(' BLOCK',J,':',STRSUM);

END;

WRITELN;

WRITELN(' ENCIPHERED TEXT(HILL CIPHER):');

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

WRITELN(' ',STRTXT);

writeln;

END;

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(' 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]:= HOLDB[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;

writeln;

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(' LIST OF INTEGERS TO DECIPHER USING AFFINE TRANSFORMATION');

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

WRITELN;

FOR K:= 1 TO NUMCHARS DO

BEGIN

WRITE(Y[K],' ');

END;

WRITELN;

WRITELN(' DECIPHERED TEXT USING AFFINE TRANSFORM:');

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;

ENCIPHER;

ENCIPHER2;

DECIPHER;

DECIPHER2;

readln;

end.

Running the program we obtain:

Enciphered Blocks:

$16 \: 21 \: 17$

$12 \: 7 \: 24$

$5 \: 23 \: 15$

$5 \: 20 \: 6$

$13 \: 5 \: 23$

Enciphered Text:

$QVRMHYFXPFUGNFX$

As a string of integers we have:

$\boxed{1621171272452315520613523}$

Deciphering we obtain:

$TODAYITWILLSNOW$

A computer science problem by Rocco Dalto

The answer is 1621171272452315520613523.

1 solution

0 pending reports