Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Program to cipher a text, new thread, fresh one |
| Date | 2015-11-03 12:48 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <n1aabd$44b$1@dont-email.me> (permalink) |
| References | (9 earlier) <164603bf-24f0-45ab-a264-776ae541bae2@googlegroups.com> <d9rjlmFkhkbU1@mid.individual.net> <fa553cd6-40cb-4f46-b3df-e04e7639953d@googlegroups.com> <n1a73k$ng2$1@dont-email.me> <d9rlq3Fl21aU1@mid.individual.net> |
On 03/11/15 11:57, Osmium wrote:
> "Richard Heathfield" wrote:
>
>> The key is decided upon by the sender and recipient. (Actually, the
>> recipient doesn't need to know the key, strictly speaking, but to know
>> it will make his life slightly easier than that of anyone listening in.)
>
> Note that Richard has several modes. That was not an example of his
> "helpful" mode.
<grin> You're right. I do, and it wasn't. To make up for it, here's one
of my Peter-and-Jane-do-techie-stuff explanations.
Vigenere is a polyalphabetic substitution cipher that uses a
substitution table along these lines:
*|ABCDEFGHI...
-+---------...
A|ABCDEFGHI...
B|BCDEFGHIJ...
C|CDEFGHIJK...
D|DEFGHIJKL...
E|EFGHIJKLM...
F|FGHIJKLMN...
G|GHIJKLMNO...
H|HIJKLMNOP...
I|IJKLMNOPQ...
and so on, in both directions: a 26x26 square. (In the body of the
table, the alphabet wraps around, like this: ...UVWXYZABCD..., where
necessary.)
The sender (often known as Alice) and the recipient (typically hailed as
Bob) agree upon a key. Say, "FACE", for example.
To encrypt the first letter of the message, Alice finds the row of the
table corresponding to that letter, and the column corresponding to the
first letter of the key. Where that row and column cross, that's the
enciphered letter. So if the message is, say, "CHEF DECIDED FIG BAD",
then Alice looks up row C and column F, and finds that they intersect at
H. So H is the first letter of the ciphertext.
The key letter F is now considered "used", and has to go to the back of
the line: from FACE to ACEF. (In a computer simulation of Vigenere, you
don't have to do that literally - modulo arithmetic will do:
k++; k %= klen;
The second letter of the message, H, is enciphered with the next letter
of the key, which is A. So Alice looks up row H and column A, and finds
the letter H there. So H is the second letter of the ciphertext too. And
let's move that key letter to the back:
Plain-text: CHEF DECIDED FIG BAD
Ciphertext: HH
Key: currently CEFA
Next, we want to encipher the E, so we look up row E column C, and we
find G (just as well - if it had been H again, that would have been
mildly spooky), and move the key letter C to the back:
Plain-text: CHEF DECIDED FIG BAD
Ciphertext: HHG
Key: currently EFAC
Now we encipher F by looking up row F and column E (the key, remember),
which gives us J, and we must remember to move the key letter E to the back:
Plain-text: CHEF DECIDED FIG BAD
Ciphertext: HHGJ
Key: currently FACE
And you will see that our key is back where it started, but that's okay
- we just plough on as if nothing had happened. So D is enciphered by
looking up row D column F and finding I there, and we remember to move
the key letter to the back:
Plain-text: CHEF DECIDED FIG BAD
Ciphertext: HHGJ I
Key: currently ACEF
and, in finest Blue Peter tradition, here's the rest of it, which I
prepared earlier:
Plain-text: CHEF DECIDED FIG BAD
Ciphertext: HHGJ IEEMIEF JNG DEI
Key: currently ACEF
Okay, if Alice is sensible she will decode that to make sure it all
still makes sense. To do that, she starts at the beginning, including
setting the key back to FACE, and she looks down the key column (F)
until she finds the ciphertext letter (H). Then she reads across to the
left, to get the plaintext letter (C). She moves that key letter to the
back as before, and does the same with the next ciphertext letter, and
so on, until she's decoded the whole thing.
I am not as sensible as Alice, so I didn't bother. (Did I get it right
anyway? I don't know. I expect so.)
Alice can now squish out all the spaces if she wants, and send the
ciphertext to Bob, who can decipher it as explained above.
Eve, an eavesdropper, is listening in on the radio, and she copies down
the Morse code beeps and turns them into ciphertext letters.
To read the message, she first has to find out the key length. This she
does by offsetting the message against itself by all plausible key
lengths, and counting how many times a letter appears in the same column
in both rows:
HHGJIEEMIEFJNGDEI
*HHGJIEEMIEFJNGDEI
-1----1---------- = 2
HHGJIEEMIEFJNGDEI
**HHGJIEEMIEFJNGDEI
----------------- = 0 (not unusual for such a short message)
HHGJIEEMIEFJNGDEI
***HHGJIEEMIEFJNGDEI
---------1------- = 1
HHGJIEEMIEFJNGDEI
****HHGJIEEMIEFJNGDEI
--------11------- = 2
and so on, up to the whole length of the message if need be.
For such a short message, the result is a little ambiguous, but for a
message of a reasonable length there is a definite "spike" when we have
the key length or a multiple thereof.
I know that sounds a little wobbly, but in practice it really does work.
Having ascertained the key length, we divide the message up into rows,
one key's worth per row:
HHGJ
IEEM
IEFJ
NGDE
I
The point here is that, in any given *column*, every ciphertext letter
was encrypted using the *same* key letter. At this point, we are able to
use the same simple cracking technique (frequency analysis) as works for
ordinary cryptograms (monoalphabetic substitution ciphers). And in
practice we need only find 'e', because everything else will fall into
place.
So, in very short order, we can read the message even if we don't have
the key.
This has been a long article with not much C, so let's have some C now.
The following program performs a Kasiski examination for you. It tries
every possible key length, and gives you the number of matches for that
key length (the higher the match count, the more likely it is that you
have the right key length). The output is in CSV format for easy import
into a spreadsheet and sorting by matches.
The "get the size of the file" function is a bodge, of course. In real
life, I use stat() - this is a for-comp.lang.c-only edited version.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
size_t get_file_length(const char *filename)
{
size_t count = 0;
FILE *fp = fopen(filename, "rb");
if(fp != NULL)
{
while(getc(fp) != EOF)
{
++count;
}
fclose(fp);
}
return count;
}
void get_key_length(unsigned char *buf,
size_t len,
unsigned char *compare)
{
unsigned long *result = calloc(len, sizeof *result);
if(result != NULL)
{
size_t offset = 0;
while(++offset < len)
{
size_t whichbyte = 0;
while(whichbyte < len)
{
if(compare[offset + whichbyte] ==
buf[whichbyte])
{
++result[offset];
}
++whichbyte;
}
}
printf("Offset,Matches\n");
for(offset = 0; offset < len; offset++)
{
if(result[offset] > 0)
{
printf("%lu,%lu\n",
(unsigned long)offset,
result[offset]);
}
}
free(result);
}
else
{
fprintf(stderr,
"Couldn't allocate storage for results.\n");
}
}
int main(int argc, char **argv)
{
if(argc > 1)
{
size_t len = get_file_length(argv[1]);
unsigned char *file = malloc(len);
unsigned char *comparator = malloc(2 * len);
if(file != NULL && comparator != NULL)
{
FILE *fp = fopen(argv[1], "rb");
if(fp != NULL)
{
size_t bytes = fread(file, 1, len, fp);
if(bytes == len)
{
memcpy(comparator, file, len);
memcpy(comparator + len, file, len);
get_key_length(file, len, comparator);
}
else
{
fprintf(stderr,
"File read error on %s - needed"
" %lu bytes, got %lu bytes.\n",
argv[1],
(unsigned long)len,
(unsigned long)bytes);
}
fclose(fp);
}
else
{
fprintf(stderr,
"Can't open %s for reading.\n",
argv[1]);
}
}
else
{
fprintf(stderr,
"Insufficient memory - need %lu bytes.\n",
(unsigned long)len);
}
free(comparator); /* NB free(NULL) is a
guaranteed NOP */
free(file);
}
else
{
fprintf(stderr,
"Specify a filename for Kasiski to examine.\n");
}
return 0;
}
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Program to cipher a text, new thread, fresh one Alla _ <modelling.data@gmail.com> - 2015-10-30 08:23 -0700
Re: Program to cipher a text, new thread, fresh one Bartc <bc@freeuk.com> - 2015-10-30 15:39 +0000
Re: Program to cipher a text, new thread, fresh one Alla _ <modelling.data@gmail.com> - 2015-10-30 09:33 -0700
Re: Program to cipher a text, new thread, fresh one Richard Heathfield <rjh@cpax.org.uk> - 2015-11-01 09:33 +0000
Re: Program to cipher a text, new thread, fresh one Mark Storkamp <mstorkamp@yahoo.com> - 2015-10-30 11:17 -0500
Re: Program to cipher a text, new thread, fresh one Alla _ <modelling.data@gmail.com> - 2015-10-30 09:32 -0700
Re: Program to cipher a text, new thread, fresh one Richard Heathfield <rjh@cpax.org.uk> - 2015-11-01 09:38 +0000
Re: Program to cipher a text, new thread, fresh one "Osmium" <r124c4u102@comcast.net> - 2015-10-30 10:55 -0600
Re: Program to cipher a text, new thread, fresh one Richard Heathfield <rjh@cpax.org.uk> - 2015-11-01 10:07 +0000
Re: Program to cipher a text, new thread, fresh one Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-01 10:42 +0000
Re: Program to cipher a text, new thread, fresh one Richard Heathfield <rjh@cpax.org.uk> - 2015-11-01 11:35 +0000
Re: Program to cipher a text, new thread, fresh one James Kuyper <jameskuyper@verizon.net> - 2015-11-01 08:33 -0500
Re: Program to cipher a text, new thread, fresh one Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-01 16:09 +0000
Re: Program to cipher a text, new thread, fresh one Bartc <bc@freeuk.com> - 2015-11-02 12:43 +0000
Re: Program to cipher a text, new thread, fresh one Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-02 13:25 +0000
Re: Program to cipher a text, new thread, fresh one Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-02 06:13 -0800
Re: Program to cipher a text, new thread, fresh one Keith Thompson <kst-u@mib.org> - 2015-11-01 12:26 -0800
Re: Program to cipher a text, new thread, fresh one supercat@casperkitty.com - 2015-11-01 07:59 -0800
Re: Program to cipher a text, new thread, fresh one Richard Heathfield <rjh@cpax.org.uk> - 2015-11-02 13:48 +0000
Re: Program to cipher a text, new thread, fresh one Bartc <bc@freeuk.com> - 2015-11-02 14:06 +0000
Re: Program to cipher a text, new thread, fresh one Richard Heathfield <rjh@cpax.org.uk> - 2015-11-02 14:51 +0000
Re: Program to cipher a text, new thread, fresh one Bartc <bc@freeuk.com> - 2015-11-02 15:48 +0000
Re: Program to cipher a text, new thread, fresh one Richard Heathfield <rjh@cpax.org.uk> - 2015-11-02 16:00 +0000
Re: Program to cipher a text, new thread, fresh one asetofsymbols@gmail.com - 2015-11-03 01:40 -0800
Re: Program to cipher a text, new thread, fresh one Richard Heathfield <rjh@cpax.org.uk> - 2015-11-03 11:16 +0000
Re: Program to cipher a text, new thread, fresh one "Osmium" <r124c4u102@comcast.net> - 2015-11-03 05:21 -0600
Re: Program to cipher a text, new thread, fresh one asetofsymbols@gmail.com - 2015-11-03 03:41 -0800
Re: Program to cipher a text, new thread, fresh one Richard Heathfield <rjh@cpax.org.uk> - 2015-11-03 11:53 +0000
Re: Program to cipher a text, new thread, fresh one "Osmium" <r124c4u102@comcast.net> - 2015-11-03 05:57 -0600
Re: Program to cipher a text, new thread, fresh one Richard Heathfield <rjh@cpax.org.uk> - 2015-11-03 12:48 +0000
Re: Program to cipher a text, new thread, fresh one Rosario19 <Ros@invalid.invalid> - 2015-11-04 09:09 +0100
Re: Program to cipher a text, new thread, fresh one Rosario19 <Ros@invalid.invalid> - 2015-11-04 09:37 +0100
Re: Program to cipher a text, new thread, fresh one Alla _ <modelling.data@gmail.com> - 2015-11-04 07:09 -0800
Re: Program to cipher a text, new thread, fresh one "Osmium" <r124c4u102@comcast.net> - 2015-11-03 05:53 -0600
Re: Program to cipher a text, new thread, fresh one asetofsymbols@gmail.com - 2015-11-03 04:29 -0800
Re: Program to cipher a text, new thread, fresh one "Osmium" <r124c4u102@comcast.net> - 2015-11-03 06:42 -0600
Re: Program to cipher a text, new thread, fresh one Geoff <geoff@invalid.invalid> - 2015-11-01 08:07 -0800
Re: Program to cipher a text, new thread, fresh one Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-02 02:26 -0800
Re: Program to cipher a text, new thread, fresh one Rosario19 <Ros@invalid.invalid> - 2015-11-06 07:53 +0100
Re: Program to cipher a text, new thread, fresh one Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-07 10:01 -0800
Re: Program to cipher a text, new thread, fresh one Alla _ <modelling.data@gmail.com> - 2015-10-30 10:50 -0700
Re: Program to cipher a text, new thread, fresh one Alla _ <modelling.data@gmail.com> - 2015-10-30 10:53 -0700
Re: Program to cipher a text, new thread, fresh one Barry Schwarz <schwarzb@dqel.com> - 2015-10-30 11:52 -0700
Re: Program to cipher a text, new thread, fresh one Alla _ <modelling.data@gmail.com> - 2015-10-30 12:12 -0700
Re: Program to cipher a text, new thread, fresh one Barry Schwarz <schwarzb@dqel.com> - 2015-10-30 21:05 -0700
Re: Program to cipher a text, new thread, fresh one Alla _ <modelling.data@gmail.com> - 2015-10-30 23:58 -0700
Re: Program to cipher a text, new thread, fresh one Barry Schwarz <schwarzb@dqel.com> - 2015-10-31 03:09 -0700
Re: Program to cipher a text, new thread, fresh one Alla _ <modelling.data@gmail.com> - 2015-10-31 03:47 -0700
Re: Program to cipher a text, new thread, fresh one Barry Schwarz <schwarzb@dqel.com> - 2015-10-31 11:42 -0700
Re: Program to cipher a text, new thread, fresh one Barry Schwarz <schwarzb@dqel.com> - 2015-10-30 12:04 -0700
Re: Program to cipher a text, new thread, fresh one Alla _ <modelling.data@gmail.com> - 2015-10-30 12:10 -0700
Re: Program to cipher a text, new thread, fresh one "Osmium" <r124c4u102@comcast.net> - 2015-10-30 13:17 -0600
Re: Program to cipher a text, new thread, fresh one Alla _ <modelling.data@gmail.com> - 2015-10-31 00:04 -0700
Re: Program to cipher a text, new thread, fresh one Alla _ <modelling.data@gmail.com> - 2015-10-31 00:25 -0700
Re: Program to cipher a text, new thread, fresh one Keith Thompson <kst-u@mib.org> - 2015-10-30 12:34 -0700
Re: Program to cipher a text, new thread, fresh one Alla _ <modelling.data@gmail.com> - 2015-10-30 21:49 -0700
Re: Program to cipher a text, new thread, fresh one Keith Thompson <kst-u@mib.org> - 2015-10-31 13:18 -0700
Re: Program to cipher a text, new thread, fresh one Alla _ <modelling.data@gmail.com> - 2015-10-31 00:29 -0700
Re: Program to cipher a text, new thread, fresh one Alla _ <modelling.data@gmail.com> - 2015-10-31 01:12 -0700
Re: Program to cipher a text, new thread, fresh one Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-31 12:24 +0000
Re: Program to cipher a text, new thread, fresh one Alla _ <modelling.data@gmail.com> - 2015-10-31 06:11 -0700
Re: Program to cipher a text, new thread, fresh one Bartc <bc@freeuk.com> - 2015-10-31 15:58 +0000
Re: Program to cipher a text, new thread, fresh one Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-31 17:37 +0000
Re: Program to cipher a text, new thread, fresh one Bartc <bc@freeuk.com> - 2015-10-31 18:14 +0000
Re: Program to cipher a text, new thread, fresh one Keith Thompson <kst-u@mib.org> - 2015-10-31 13:29 -0700
Re: Program to cipher a text, new thread, fresh one Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-31 20:35 +0000
Re: Program to cipher a text, new thread, fresh one Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-31 20:32 +0000
Re: Program to cipher a text, new thread, fresh one Rosario19 <Ros@invalid.invalid> - 2015-11-04 09:50 +0100
csiph-web