Re: OTP_and_the_proof_thereof: Discussion_Topic
- From: gordonb.mms3d@xxxxxxxxxxx (Gordon Burditt)
- Date: Wed, 07 Jan 2009 15:35:58 -0600
Quote from, ? Handbook of Applied Cryptography? ? A.Menezes , Paul VanCorrection
Oorschoot , S Vanstone. :-
? The One Time Pad can be shown to be theoretically unbreakable. That
is, if a cryptanalyst has a cipher text string c1 , c2 , c3 , ???
ct , encrypted using a random keystring which has been used only
once, the cryptanalyst can do no better than guess at the plaintext
being any binary string of length ?t? (i.e t-bit binary strings are
equally likely as plaintext). It has been proven that that to realize
an unbreakable system requires a random key of the same length as the
message ? ? Unquote.
The latter part ??it has been proven . . . etc? - comes from
information theory.
Let the reader be assured that there is no heavy mathematics unseen
in the present background and it is only necessary to understand the
descriptive logic that follows in order to prove the OTP. Regarding
the sentence? t-bit binary strings are equally likely as plaintext ?,
the cryptanalyst is guessing his way along and is in the dark.
Suppose he assigns some plaintext to the first cipher text c1, there
are two possibilities, he may be right or he may be wrong in his
guess. The solution space is 2.
Assigning a plaintext to c2 as his next guess means he may again be
either right or wrong and two more possibilities are added to the
solution space making it four for the first two ciphertext. Ditto for
c3 adds two more possibilities to the solution space making it eight
now for three guesses. Clearly, each cipher text that is guessed adds
another two possibilities to the solution space.
Collecting these results,
C1 => 2 = 2**1 of plaintext strings that are each 2 characters long.
C2 => 4 = 2**2 of plaintext strings that are each 4 characters long.
C3 => 8 = 2**3 of plaintext strings that are each 8 characters long.
Ct => 2 **t of plaintext strings that are each ?t? characters long.
This number 2** t now represents the size of the possibilities of
plaintext strings in the solution space and clearly this a binary
number that is ?t? bits long. (i.e t-bit binary strings are equally
likely as plaintext is thus explained)
Suppose a guess for some cipher text is a ?right? one (an imaginary
hypothetical situation only) it will not be added to the solution
space as a pair since it is correct as 'one'. The solution space then
becomes ?t -1? in extent of plaintext strings that are each ?t?
characters long. For a correct plaintext string all of the guesses
will have to be correct and the size of the solution space will then
be 2** ( t ? t ) i.e 2** 0 = 1 i.e there is only one element in the
solution space that can be a correct plaintext string ?t? characters
long when all the guesses are correct. A cryptanalyst can only guess
at what that string might be among all of the 2**t candidates in the
solution space.
Because of the randomness of the cipher text string, it is impossible
for a cryptanalyst to know if any of his guesses are correct because -
a) the ciphertext being 'scientifically' random, all guesses are
equally probable and 2) there is no rule to the string that might be
mimicked in any way by a brute force program that exhaustively tests
every possibility, or by approximating numerical analysis, or by
lexical probability methods (linguistic probability possibly). This
latter is underwritten by the fact of the cipher text being
alphanumeric in nature and therefore has no methodology to it and also
by being composed of the 256 characters of ASCII that are in part
comprised of the un-writable characters of the code. Alphanumeric is
tantamount to ?bad data? to numerical methods and to lexical methods
alike.
That is what randomness means ? equal probability between the elements
of the keypad in satisfying any cryptanalysis ? no rule to the key
string that might enable the elements to be identified by having
determinable ?order?.
The foregoing description is deliberately expanded here and
experienced readers should not feel patronized by the simplistic
approach. It is normally demonstrated as an XORing exercise that may
also be simulated as a customised form of binary addition.
An important point here is that the OTP depends on the randomness of
the keypads - that imparts randomness to a non-random string of
plaintext - to make a random string of cipher text. A fundamental
condition is that all three of these strings have the same numerical
length and the keypad is used only once ever. This latter condition
emanates from principles of information theory.
Incidentally,
Although this expansion uses binary arithmetic it does not mean that
byte representation of ASCII is the vogue in the OTP cipher. The
computer program exclusively uses denary representation of ASCII in
the attributes of the code when paging the elements ASCII in ant
program. Binary representation is essential to information theory on
the other hand only, because of the bi-stable state of the electrical
equipment necessary to measure pulses.
The writer is unapologetically promoting his implementation of the OTP
being called ASCII_Pad Cipher. The foregoing text applies to this
cipher in particular as well as being generally true for any OTP.
Le meas - adacrypt
<either right or wrong and two more possibilities are added to the
<solution space making it four for the first two ciphertext. Ditto
for
<c3 adds two more possibilities to the solution space making it eight
<now for three guesses. Clearly, each cipher text that is guessed
adds
<another two possibilities to the solution space.
This should read:
Assigning a plaintext to c2 as his next guess means he may again be
either right or wrong and two more possibilities are added to the
solution space making it four for the first two ciphertext. Ditto for
c3 adds two more possibilities to the solution space making it eight
now for three guesses. Clearly, each cipher text that is guessed
doubles the existing solution space.
<Collecting these results,
<C1 => 2 = 2**1 of plaintext strings that are each 2 characters long.
<C2 => 4 = 2**2 of plaintext strings that are each 4 characters long.
<C3 => 8 = 2**3 of plaintext strings that are each 8 characters long.
This should read :
Collecting these results,
C1 => 2 = 2**1 of plaintext strings that are each 1 characters long.
C2 => 4 = 2**2 of plaintext strings that are each 2 characters long.
C3 => 8 = 2**3 of plaintext strings that are each 3 characters long.
As I recall, the last time this came up, your Ascii_Pad cipher does
*not* use a purely-random key at least as long as the message, it
is *not* a One Time Pad, it is a Many Snake Pad, and the post I am
replying to describes why it is *NOT* theoretically unbreakable
better than I did in the last discussion.. The same applies to
"vector cryptography".
Note that it's possible to have what appears to be an enormous key
that doesn't really provide the results of a large key. For example,
I could select a random number N from 0-255 for each *BIT* of the
message, and run the message through "rot N" for each of the numbers
in turn. It looks like I've got a key 8 times the length of the
message, right? Well, there are only 26 possible ciphertexts that
can come out of this.
.
- Follow-Ups:
- Re: OTP_and_the_proof_thereof: Discussion_Topic
- From: WTShaw
- Re: OTP_and_the_proof_thereof: Discussion_Topic
- References:
- OTP and the proof thereof – Discussion Topic.
- From: austin . obyrne
- Re: OTP and the proof thereof – Discussion Topic.
- From: austin . obyrne
- OTP and the proof thereof – Discussion Topic.
- Prev by Date: Re: Non-expanding transform for designing nonmalleable encryption mode.
- Next by Date: Re: Non-expanding transform for designing nonmalleable encryption mode.
- Previous by thread: Re: OTP and the proof thereof – Discussion Topic.
- Next by thread: Re: OTP_and_the_proof_thereof: Discussion_Topic
- Index(es):
Relevant Pages
|
