A computer science problem by Rocco Dalto

Computer Science Level pending

A data base B contains four files $b_{1} = (10000001)_{2}, \: b_{2} = (10001010)_{2}, \: b_{3} = (10011001)_{2}, \: b_{4} = (00000001)_{2}.$

Let the prime divisors $m_{1} = 131, \: m_{2} = 139, \: m_{3} = 157, \: m_{4} = 2$ be the read sub keys.

Encipher the data base using the Chinese remainder theorem and determine the Cipher text $X.$

Convert each $b_{j}$ in base 2 to base 10 prior to doing the problem, then set up each congruence $X \equiv b_{j} \mod {m_{j}}$ where $(1 <= j <= 4)$ and solve for $X$ .

Given $N$ files in a database and $N$ prime divisors(read sub keys), write a general program(in any language) to encipher the data base using the Chinese remainder theorem and determine the Cipher text $X.$ . Do not use any predefined functions or procedures.

Refer to previous problem. . .

The answer is 389199.

1 solution

Rocco Dalto
Mar 14, 2017

I wrote the program in Free Pascal:

$Begin \: {problem}$

I moved functions, procedures and types from my unit(mathunit) into the main program.

Solve each congruence $X \equiv b_{j} \mod {m_{j}}$ where $(1 <= j <= n)$ and $(m_j,m_k)= 1$ for $j <> k$ and each $b_{j}$ has been converted to base $10$ .

program Applicationextensionforcheckingfunctions;

uses crt;

type chinesearray = array[1 .. 10000] of longint;

    strtype = array[1 .. 10000] of string;

var n:longint;

b,m,datafile:chinesearray;

bool,bool2:boolean;

base:longint;

strdata:string;

c:strtype;

function INTpower(base,exponent:integer):longint;

var product,k:longint;

begin{INTpower}

product:= 1;

 for k:= 1 to exponent do

      product:= product * base;

 INTpower:= product;

end;{INTpower}

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

var j,k:longint;

begin

bool:= true;

for j:= 1 to n do

begin

for k:= j + 1 to n do

begin

if m[j] = m[k] then

bool:= false;

end;

procedure checkprimes;

var k,j:longint;

begin

bool2:= true;

for j:= 1 to n do

begin

if not(prime(m[j])) then

begin

bool2:= false;

end;

PROCEDURE GETSTRLIST(STRVAR:string; VAR STRITEM:STRTYPE; NUMTERMS:INTEGER);

VAR STR,STRSUM:string;

K,N,SIZESTR:INTEGER;

BEGIN

STR:= STRVAR;

SIZESTR:= LENGTH(STR);

N:= 1;

FOR K:= 1 TO NUMTERMS DO

BEGIN

STRSUM:= '';

IF STR[N] = ' ' THEN N:= N + 1;

WHILE (STR[N] <> ' ') AND (N <= SIZESTR) DO

BEGIN

STRSUM:= STRSUM + STR[N];

N:= N + 1;

END;

STRITEM[K]:= STRSUM;

END;

procedure getinput;

var j:longint;

begin

writeln('Enter base b <= 35');

readln(base); {use safeguard here}

writeln('Enter number of prime divisors');

readln(n);

n:= abs(trunc(n)); {play safe}

writeln('Enter list of distinct prime divisors m(j)_(1 <= j <= ',n,')');

for j:= 1 to n do

begin

read(m[j]);

m[j]:= abs(trunc(m[j])); {play safe}

end;

checkprimes;

while not(bool2) do

begin

writeln('Renter list of prime divisors');

for j:= 1 to n do

begin

read(m[j]);

m[j]:= abs(trunc(m[j]));

end;

checkprimes;

end;

if bool2 then

begin

safeguard;

while not(bool) do

begin

writeln('Renter list of prime divisors');

for j:= 1 to n do

begin

read(m[j]);

m[j]:= abs(trunc(m[j]));

end;

safeguard;

end;

readln;

writeln('Enter list of numbers in base ',base);

read(strdata);

getstrlist(strdata,c,n);

end;

procedure changeback(k:char; var j:string);
{Not needed for this problem since using base 2}

begin{change}

IF upcase(K) = '0' then J:= '0';

IF upcase(K) = '1' THEN J:= '1';

IF upcase(K) = '2' THEN J:= '2';

IF upcase(K) = '3' THEN J:= '3';

IF upcase(K) = '4' THEN J:= '4';

IF upcase(K) = '5' THEN J:= '5';

IF upcase(K) = '6' THEN J:= '6';

IF upcase(K) = '7' THEN J:= '7';

IF upcase(K) = '8' THEN J:= '8';

IF upcase(K) = '9' THEN J:= '9';

IF upcase(K) = 'A' THEN J:= '10';

IF upcase(K) = 'B' THEN J:= '11';

IF upcase(K) = 'C' THEN J:= '12';

IF upcase(K) = 'D' THEN J:= '13';

IF upcase(K) = 'E' THEN J:= '14';

IF upcase(K) = 'F' THEN J:= '15';

IF upcase(K) = 'G' THEN J:= '16';

IF upcase(K) = 'H' THEN J:= '17';

IF upcase(K) = 'I' THEN J:= '18';

IF upcase(K) = 'J' THEN J:= '19';

IF upcase(K) = 'K' THEN J:= '20';

IF upcase(K) = 'L' THEN J:= '21';

IF upcase(K) = 'M' THEN J:= '22';

IF upcase(K) = 'N' THEN J:= '23';

IF upcase(K) = 'O' THEN J:= '24';

IF upcase(K) = 'P' THEN J:= '25';

IF upcase(K) = 'Q' THEN J:= '26';

IF upcase(K) = 'R' THEN J:= '27';

IF upcase(K) = 'S' THEN J:= '28';

IF upcase(K) = 'T' THEN J:= '29';

IF upcase(K) = 'U' THEN J:= '30';

IF upcase(K) = 'V' THEN J:= '31';

IF upcase(K) = 'W' THEN J:= '32';

IF upcase(K) = 'X' THEN J:= '33';

IF upcase(K) = 'Y' THEN J:= '34';

IF upcase(K) = 'Z' THEN J:= '35';

END;{CHANGE}

function num_base10(num:string; baseb:longint):longint;

var sum:longint;

strnum,strdigit:string;

digit,error,j:longint;

begin

sum:= 0;

strnum:= num;

for j:= 1 TO length(strnum) DO

begin

if baseb >= 10 then {not needed for this problem}

begin

changeback(strnum[j],strdigit);

val(strdigit,digit,error);

end

else

val(strnum[j],digit,error);

sum:= sum + digit * intpower(baseb,length(strnum) - j);

end;

num_base10:= sum;

end;

function s(m,a:chinesearray; n:longint):longint;

var j,k,sum,prod:longint;

MK,inverse:chinesearray;

begin

prod:= 1;

for j:= 1 to n do

begin

prod:= prod * m[j];

end;

for j:= 1 to n do

begin

Mk[j]:= prod div m[j];

end;

for k:= 1 to n do

begin

for j:= 0 to m[k] - 1 do

begin

if Mk[k] * j mod m[k] = 1 then

inverse[k]:= j;

end;

sum:= 0;

for j:= 1 to n do

begin

sum:= sum + a[j] * Mk[j] * inverse[j];

end;

s:= sum mod prod;

end;

procedure encipher;

var k,j:longint;

begin

writeln(' Enciphered Data');

for k:= 1 to n do

begin

b[k]:= num_base10(c[k],2);

end;

for j:= 1 to n do

begin

writeln('(',s(m,b,n),',',m[j],',',base,')');

end;

begin

getinput;

encipher;

readln;

clrscr;

end.

The output is: $(389199,131,2), (389199,139,2), (389199, 157,2), (389199,2,2).$

The Cipher text $X = \boxed{389199}$ .

$End \: {problem}$ .

Given $(389199,131), (389199,139), (389199, 157), (389199,2)$ we could now decipher the enciphered text to obtain the data files.

Writing a program to decipher:

I moved functions, procedures and types from my unit(mathunit) into the main program.

To decipher use $b_{j} \equiv X \mod {m_{j}}$ , where $(1 <= j <= n)$ , then convert each $b_{j}$ to base 2.

program Applicationextensionforcheckingfunctions;

uses crt;

type chinesearray = array[1 .. 10000] of longint;

var n:longint;

b,m:chinesearray;

bool,bool2:boolean;

base,X:longint;

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

var j,k:longint;

begin

bool:= true;

for j:= 1 to n do

begin

for k:= j + 1 to n do

begin

if m[j] = m[k] then

bool:= false;

end;

procedure checkprimes;

var k,j:longint;

begin

bool2:= true;

for j:= 1 to n do

begin

if not(prime(m[j])) then

begin

bool2:= false;

end;

procedure getinput;

var j:longint;

begin

writeln('Enter base b <= 35');

readln(base); {use safeguard here}

writeln('Enter number of prime divisors');

readln(n);

n:= abs(trunc(n)); {play safe}

writeln('Enter list of distinct prime divisors m(j)_(1 <= j <= ',n,')');

for j:= 1 to n do

begin

read(m[j]);

m[j]:= abs(trunc(m[j])); {play safe}

end;

checkprimes;

while not(bool2) do

begin

writeln('Renter list of prime divisors');

for j:= 1 to n do

begin

read(m[j]);

m[j]:= abs(trunc(m[j]));

end;

checkprimes;

end;

if bool2 then

begin

safeguard;

while not(bool) do

begin

writeln('Renter list of prime divisors');

for j:= 1 to n do

begin

read(m[j]);

m[j]:= abs(trunc(m[j]));

end;

safeguard;

end;

writeln('Enter X for each divisor m(j)');

readln(X);

end;

procedure change(var k:string); {again, not needed here since using base 2.}

begin{change}

IF K = '10' THEN K:= 'A';

IF K = '11' THEN K:= 'B';

IF K = '12' THEN K:= 'C';

IF K = '13' THEN K:= 'D';

IF K = '14' THEN K:= 'E';

IF K = '15' THEN K:= 'F';

IF K = '16' THEN K:= 'G';

IF K = '17' THEN K:= 'H';

IF K = '18' THEN K:= 'I';

IF K = '19' THEN K:= 'J';

IF K = '20' THEN K:= 'K';

IF K = '21' THEN K:= 'L';

IF K = '22' THEN K:= 'M';

IF K = '23' THEN K:= 'N';

IF K = '24' THEN K:= 'O';

IF K = '25' THEN K:= 'P';

IF K = '26' THEN K:= 'Q';

IF K = '27' THEN K:= 'R';

IF K = '28' THEN K:= 'S';

IF K = '29' THEN K:= 'T';

IF K = '30' THEN K:= 'U';

IF K = '31' THEN K:= 'V';

IF K = '32' THEN K:= 'W';

IF K = '33' THEN K:= 'X';

IF K = '34' THEN K:= 'Y';

IF K = '35' THEN K:= 'Z';

end;

function func_convert(number,base:longint):string;

var quot,remainder,j,m:longint;

a:chinesearray;

strvar,strsum:string;

begin{convert}

quot:= abs(number);

j:= 0;

while quot >= 1 do begin{loop}

      remainder:= quot mod base;

      quot:= quot div base;

      j:= j + 1;

      a[j]:= remainder;

  end;{loop}

  strsum:= '';

       for m:= 1 to j do

 begin{m}

str(a[j - m + 1], strvar);

change(strvar); {for base >= 10, not needed here}

strsum:= strsum + strvar;

end;{m}

func_convert:= strsum;

end;{convert}

procedure decipher;

var j:longint;

begin

writeln(' Deciphered data ');

for j:= 1 to n do

begin

b[j]:= X mod m[j];

writeln(func_convert(b[j],base));

end;

begin

getinput;

decipher;

readln;

clrscr;

end.

The program to decipher outputs the data base files: $(10000001)_{2}, \: (10001010)_{2}, \: (10011001)_{2}, \: (00000001)_{2}.$

A computer science problem by Rocco Dalto

The answer is 389199.

1 solution

0 pending reports