Welcome Guest [Log In] [Register]
Welcome to Crypto. We hope you enjoy your visit.


You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free.


Join our community!


If you're already a member please log in to your account to access all of our features:

Username:   Password:
Add Reply
Linear Congruential Prng
Topic Started: Feb 4 2007, 05:03 PM (284 Views)
jdege Feb 4 2007, 05:03 PM Post #1
Member Avatar
Elite member
[ * * * * * ]
 I'm still working through the problems from Cryptanalysts' Corner. The second problem is:

Code:
 
39817 13888 28485 52755 10800 25928
47239 46844 56663 80250 81105 02689
60895 42733 43242 14205 74291 34545
33500 01642 71142 07178 71492 15659
33357 15368 12


This is encoded with a linear congruential pseudo-random number generator.

The plaintext is converted to integers, each letter becoming a pair of digits: A:01, B:02, Z:26.

This is added, digit-by-digit, to a keystream, mod-9.

The keystream is a sequence of four-digit integers, generated using the PRNG.

k(n+1) = k(n) * A + B (mod C)

A, B, C, and the seed k(0) compose the key.

The crib is "BRIANWINKEL", with the 'W' represented by the 22nd, 23rd, or 24th pair of digits.
When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl.
Offline Profile Quote Post Goto Top
 
insecure Feb 4 2007, 10:11 PM Post #2
Elite member
[ * * * * * ]
 If it's modulo 9, how come there are several 9s in the ciphertext? Do you mean mod 10?
Offline Profile Quote Post Goto Top
 
jdege Feb 4 2007, 10:54 PM Post #3
Member Avatar
Elite member
[ * * * * * ]
insecure
Feb 4 2007, 10:11 PM
If it's modulo 9, how come there are several 9s in the ciphertext? Do you mean mod 10?

Yes, I did mean modulo 10.

There was an article on how to break this sort of cipher in the first issue of Cryptologia:

``Cracking" a Random Number Generator by James Reeds. Volume I, Number 1, January 1977.20-26
When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl.
Offline Profile Quote Post Goto Top
 
insecure Feb 4 2007, 11:43 PM Post #4
Elite member
[ * * * * * ]
 If we're going to crack it, it's much simpler if we know exactly how it was enciphered, and a computer program is a great way to describe a process exactly. So - if I'm understanding you correctly, encryption goes like this:

Code:
 

#include <ctype.h>
#include <stdio.h>
#include <string.h>

int prng(int A, int B, int C, int k)
{
 return k * (A * B) % C;
}

void encrypt(char *s, int A, int B, int C, int k)
{
 char alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 int ch;
 char *ptr = NULL;
 int code;
 int count = 0;
 while(*s)
 {
   if(isalpha(*s))
   {
     ch = toupper(*s);  /* change to upper case to make searching quicker */
     code = strchr(alphabet, ch) - alphabet; /* find the letter position */
     /* code is now in the range 0 to 25 */
     ++code; /* 1 to 26 */

     digit = code / 10;  /* get first digit of two-digit pair */
     digit += k;    /* add to key */
     digit %= 10;  /* drop any leading digits */
     k = prng(A, B, C, k);  /* change the key */

     /* output */
     printf("%d", digit); /* write the digit */
     ++count;
     if(count % 5 == 0)
     {
       putchar(count == 30 ? '\n' : ' ')
       count %= 30;
     }

     digit = code % 10;    /* get the second digit in the pair */
     digit += k;    /* add to key */
     digit %= 10;  /* drop any leading digits */
     k = prng(A, B, C, k);  /* change the key */

     /* output */
     printf("%d", digit);  /* write the digit */
     ++count;
     if(count % 5 == 0)
     {
       putchar(count == 30 ? '\n' : ' ')
       count %= 30;
     }
   }
   ++s;  /* next character */
 }
 printf("\n"); /* terminate the line */
}




I particularly draw your attention to the fact that, according to the interpretation above, k is used unmodified to encrypt the first digit of the first (translated-to-01-to-26) character, and then k is modified by the PRNG.

Is that basically right?
Offline Profile Quote Post Goto Top
 
jdege Feb 5 2007, 04:56 AM Post #5
Member Avatar
Elite member
[ * * * * * ]
insecure
Feb 4 2007, 11:43 PM
If we're going to crack it, it's much simpler if we know exactly how it was enciphered, and a computer program is a great way to describe a process exactly. So - if I'm understanding you correctly, encryption goes like this:

When I start messing about with a new encryption system, I like to write a program that will handle the encryption and decryption, just so I can test my understanding of how it works.

Railfence, for example, seemed like a very simple thing. But laying out the positions for decryption turned out to be more complicated than I would have expected, before I started trying to code it.

As for your code, you don't quite have it.

Each element of the key stream is an integer in [0,10,000). That is, each integer is four digits. And those four digits are used to encrypt four digits (two characters) of the plaintext. Then the PRNG is run through another cycle to create the next four digits.

It follows pretty clearly, then, that the modulus C must be less than 10,000.
When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl.
Offline Profile Quote Post Goto Top
 
loki Feb 5 2007, 12:30 PM Post #6
Advanced Member
[ * * * ]
 My first go at railfence, I attempted it by using this method. I had two arrays A and B, read first put it in A and next char goes into B, I padded with an 'X'. It worked preety good for me.
c(x) = 3x3 + x2 + x + 2; Find the inverse
Offline Profile Quote Post Goto Top
 
jdege Feb 5 2007, 01:26 PM Post #7
Member Avatar
Elite member
[ * * * * * ]
loki
Feb 5 2007, 12:30 PM
My first go at railfence, I attempted it by using this method. I had two arrays A and B, read first put it in A and next char goes into B, I padded with an 'X'. It worked preety good for me.

That works fine for a two-rail fence. But for a five-rail fence it's a little tricky working out just how many characters go in each row.


Code:
 

. A       I
.  B     H J
.   C   G
.    D F
.     E

[/font]

Particularly if you:

1. don't pad to a complete V at the end,
2. allow an offset from the start of a V at the beginning (e.g. 1st character is placed in the third rail, where the 'C' is above).
3. read the rails off in keyword order.
When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl.
Offline Profile Quote Post Goto Top
 
1 user reading this topic (1 Guest and 0 Anonymous)
« Previous Topic · Challenges · Next Topic »
Add Reply