Key generation works as shown in the figure below, from this book.

p = 7 q = 23

In addition to p and q, we need to choose e. Let's use:

e = 5

Enter this program into a file named
**rsa.cbl**:

Create the "MODINV36" subroutine based on the modular inverse routine you created in the previous set of challenges.

IDENTIFICATION DIVISION. PROGRAM-ID. RSA. DATA DIVISION. WORKING-STORAGE SECTION. 01 WS-X PIC 9(36). 01 WS-N PIC 9(36). 01 WS-D PIC 9(36). 01 WS-P PIC 9(36). 01 WS-Q PIC 9(36). 01 WS-P1 PIC 9(36). 01 WS-Q1 PIC 9(36). 01 WS-E PIC 9(36). 01 WS-PHI PIC 9(36). 01 WS-DIV PIC 9(36). 01 WS-REM PIC 9(36). PROCEDURE DIVISION. DISPLAY "ENTER P:". ACCEPT WS-P. DISPLAY "ENTER Q:". ACCEPT WS-Q. DISPLAY "ENTER E:". ACCEPT WS-E. MULTIPLY WS-P BY WS-Q GIVING WS-N. DISPLAY "N = " WS-N SUBTRACT 1 FROM WS-P GIVING WS-P1. SUBTRACT 1 FROM WS-Q GIVING WS-Q1. MULTIPLY WS-P1 BY WS-Q1 GIVING WS-PHI. DISPLAY "PHI = " WS-PHI. DIVIDE WS-PHI BY WS-E GIVING WS-DIV REMAINDER WS-REM. IF WS-REM = 0 THEN DISPLAY "ERROR: E MUST NOT BE A DIVISOR OF PHI" STOP RUN. CALL 'MODINV36' USING WS-E, WS-PHI, WS-D. DISPLAY 'D = ' WS-D. STOP RUN.

Compile it with that file, so you can calculate RSA keys, as shown below.

## Flag CBL 7.1: Generate D (10 pts)

Calculatedfrom these values:

p = 17 q = 43 e = 5

Let's encode each character using ASCII values in base 10, forming two numbers like this:

AB

65 66

So this program will encrypt a single character with e=5:

As shown below, that character encrypts to 11.

IDENTIFICATION DIVISION. PROGRAM-ID. RSA-EN5. DATA DIVISION. WORKING-STORAGE SECTION. 01 WS-X PIC 9(36). 01 WS-N PIC 9(36). 01 WS-Y PIC 9(36). 01 WS-DIV PIC 9(36). PROCEDURE DIVISION. DISPLAY 'ENTER X:'. ACCEPT WS-X. DISPLAY 'ENTER N:'. ACCEPT WS-N. DISPLAY 'USING E = 5'. MULTIPLY WS-X BY WS-X GIVING WS-Y. MULTIPLY WS-X BY WS-Y GIVING WS-Y. MULTIPLY WS-X BY WS-Y GIVING WS-Y. MULTIPLY WS-X BY WS-Y GIVING WS-Y. DIVIDE WS-Y BY WS-N GIVING WS-DIV REMAINDER WS-Y. DISPLAY "Y = " WS-Y. STOP RUN.

## Flag CBL 7.2: Encrypt (10 pts)

Write a progam that encrypts a series of letters, as shown below.Encrypt the message

FLAGin the same manner with this public key:The result is a 12-digit number. That 12-digit number is the flag.

n = 731 e = 5

So this program will decrypt a single character:

Here's that program decrypting the ciphertext 11 we encrypted earlier with these parameters:

IDENTIFICATION DIVISION. PROGRAM-ID. RSA-DE. DATA DIVISION. WORKING-STORAGE SECTION. 01 WS-X PIC 9(36). 01 WS-N PIC 9(36). 01 WS-Y PIC 9(36). 01 WS-D PIC 9(36). 01 WS-I PIC 9(36). 01 WS-DIV PIC 9(36). PROCEDURE DIVISION. DISPLAY "ENTER Y:". ACCEPT WS-Y. DISPLAY "ENTER D:". ACCEPT WS-D. DISPLAY "ENTER N:". ACCEPT WS-N. MOVE 1 TO WS-X. PERFORM VARYING WS-I FROM 1 BY 1 UNTIL WS-I > WS-D MULTIPLY WS-Y BY WS-X GIVING WS-X DIVIDE WS-X BY WS-N GIVING WS-DIV REMAINDER WS-X END-PERFORM. DISPLAY "X = " WS-X. STOP RUN.

As shown below, that character decrypts to 65.

p = 7 q = 23 e = 5 n = 161 d = 53

## Flag CBL 7.3: Decrypt (10 pts)

Write a progam that decrypts a series of letters, as shown below.Challenge: use these parameters:

and decrypt this message:

p = 7 q = 23 e = 5 n = 161 d = 53The result is the flag.

037088026011033029008078011

## Flag CBL 7.4: Decrypt without the Key (20 pts)

Using this public key:Factor that key and find p, q, and d. Then decode this message. Each number is one encrypted letter.

n = 670661 e = 5The result is the flag.

208489 058442 151261 151261 049897 655085 248257 049897 135963

Notice that D is over 400,000 and N is over 700,000, as shown below.

p = 881 q = 883 e = 13

Now use these values:

D and N are now in the tens of millions, as shown below, and the calculation is slow, taking about 30 seconds when I did it.

p = 7349 q = 7351 e = 13

Clearly we can't handle keys much larger than this with the inefficient algorithm we've been using.

## Flag CBL 7.5: Euclid's Algorithm (20 pts)

To handle larger keys, we need a faster way to find multiplicative inverses.Write a faster function to calculate d using

Euclid's Algorithm. Change all variables to PIC 9(36), the maximum available in COBOL.Calculate

dfrom these values:The result is the flag, covered by a green rectangle in the image below.

p: 7777867 q: 8888933 e: 5

The result is 65, as shown below.

y = 198174 d = 477637 n = 777923

Now use these values:

D and N are now in the hundreds of millions, as shown below, and the calculation is slow, taking about 30 seconds when I did it.

y = 32179356 d = 24926677 n = 54022499

Clearly we can't handle keys much larger than this with the inefficient algorithm we've been using.

## Flag CBL 7.6: Modular Exponentiation (20 pts)

To handle larger keys, we need a faster way to raise numbers to high powers.Write a faster function using

modular exponentiation.Calculate

xfrom this function:with these values:

The result is the flag, covered by a green rectangle in the image below.

y: 5277319168 d: 27654768791645 n: 69136938645911

## Flag CBL 7.7: Finding Large Primes (20 pts)

Fermat's little theorem states that if p is prime and a is not divisible by p, then:So testing that condition for several random values of a can be used as evidence that p is probably prime. This page explains the Fermat primality test and its flaws in more detail.

Find the first prime number larger than this value:

The result is the flag, covered by a green rectangle in the image below.

999888777666555

## Flag CBL 7.8: Factoring a Number (20 pts)

There are faster algorithms, but simply attempting division by every odd number up to the square root of a number is sufficient to find the factors of a number.Find the lower factor of this value:

The result is the flag.

21188802353371

## Flag CBL 7.9: Decrypt without the Key (40 pts)

Using this public key:Factor that key and find p, q, and d. Then decode this message.

n = 68325320563030249 e = 3The result is a long number. Each pair of digits in that number is the ASCII code for one letter, like this:

52281470188782133The number

656667encodes the messageABCThe message is the flag.

Posted 4-13-2020 by Sam Bowne