Cryptography-Digest Digest #813, Volume #9 Thu, 1 Jul 99 06:13:03 EDT
Contents:
Quantum Computers (Greg Ofiesh)
Re: Can Anyone Help Me Crack A Simple Code? (S.T.L.)
Re: Can Anyone Help Me Crack A Simple Code? (mercury)
Re: The One-Time Pad Paradox ("Dr.Gunter Abend")
Re: A Quanitative Scale for Empirical Length-Strength (Jim Gillogly)
Re: new book (wtshaw)
Re: two questions ("Douglas A. Gwyn")
Re: Quantum Computers (Mok-Kong Shen)
Re: BLT update (long) with (rec) ciphertexts (Mok-Kong Shen)
Re: How do you make RSA symmetrical? (Gilad Maayan)
----------------------------------------------------------------------------
From: Greg Ofiesh <[EMAIL PROTECTED]>
Subject: Quantum Computers
Date: Thu, 01 Jul 1999 07:16:57 GMT
Let us begin with the following assertion that I think you will all
agree with. If a quantum computer exists, then the only form of
encryption that cannot be broken by it, or at least has half a chance
to survive an attack, is OTP. All other forms of encryption are
deterministic in nature and are not "cracked" but simply "translated"
(to convey the ease with which cryptanalysis is performed) by a quantum
computer.
Now let me make my assertion - The US government, most likely the NSA,
has operational quantum computers.
Contrary to a point raised earlier, the quantum computer is not used by
the NSA. It is simply left running - translating everything it sees on
the internet into plain text and then passing it off to storage devices.
God I wish this were not true, but I have strong reasons to believe it
is. My brother was studying how to build a quantum computer at UC
Berkeley in the early to mid 80's and talked with people from around
the country on this subject. He has little doubt that a quantum
computer exists today. In fact, talking to him, I see that the biggest
obstacle is not hardware but software, because it takes near genius to
understand the potential that exists with a quantum computer.
He tells me how he first began to think of designing an 8 state quantum
computer and then realizing that he was still thinking binary. That
the quantum computer using, say, U238, can have on orders of 238! (yes
factorial) states per atom. Now the question becomes, how many states
does present day technology support?
If a quantum computer is not operational today, it is due to the fact
that an operating system is still being developed- I am convinced that
it is not the hardware keeping it from working.
Can anyone provide any additional insight. And please don't say I am
nuts, or kook, or anything else. If that is all you have to say, get a
life or a wife and go somewhere else.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (S.T.L.)
Subject: Re: Can Anyone Help Me Crack A Simple Code?
Date: 01 Jul 1999 07:52:37 GMT
<<How did you solve for an RSA decryption key on your calculator?>>
TI-92+ calculators have near-arbitary-precision integer arithmetic. I simply
use algorithms that work with only integers, and I can find a decryption key
given an encryption key and a modulus' factorization. A condensed version of my
keygen program would go:
Prompt user for keysize, etc.
Find one random prime, half of keysize. (You know what I mean here.)
Find another random prime, again about half of the keysize.
Multiply together to get N. Get (P-1)(Q-1), and choose some public exponent R.
Find the associated secret exponent S.
Output N, R, S.
I also use the Chinese Remainder Theorem to speed up decryption and as such
give the user an option to precompute a couple of numbers useful in speeding up
the CRT step.
I got a general description of RSA from a book by Ivars Peterson, and I figured
out how to do the steps (like calculate S given R and the factors of N) from
looking at a library of number-theory functions for the TI-92. I use modified
forms of several of those functions, but sped up for my specific use. MODINV()
is one that can be used to find S. I snipped out every part of the code that
wasn't useful to me and sped up the rest. The one function I did not actually
modify (only sped up) was the modular exponentiation algorithm.
<<And how did you test to see if your numbers were prime?>>
Rabin-Miller strong psuedoprimality tests. To a single prime base, or up to 25
prime bases.
<<I have never seen this done.>>
That's because it has never been done before. :-D
<<How large are the keys you are creating? I am curious.>>
Due to TI-92+ integer precision limits, I keep moduli under 300 decimal digits.
I could push it to 307, but 300 is nice and round. 300 decimal digits, by the
way, is darn near 1024 bits. Hoo yeah! I have a munition on my calculator. I
have personally created a 250-digit key for my own experimentation and use. It
took less than an hour (I forget the actual time). The program suite is capable
of key generation, encryption with R, decryption with R, fast CRT-enhanced
encryption using S, and fast CRT-enhanced encryption using S. I don't use
message padding yet - that is the biggest "flaw" I know of. I ought to code
that some day.
-*---*-------
S.T.L. ===> [EMAIL PROTECTED] <=== BLOCK RELEASED! 2^3021377 - 1 is PRIME!
Quotations: http://quote.cjb.net Main website: http://137.tsx.org MOO!
"Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 F00FC7C8
E-mail block is gone. It will return if I'm bombed again. I don't care, it's
an easy fix. Address is correct as is. The courtesy of giving correct E-mail
addresses makes up for having to delete junk which gets through anyway. Join
the Great Internet Mersenne Prime Search at http://entropia.com/ips/ Now my
.sig is shorter and contains 3379 bits of entropy up to the next line's end:
-*---*-------
Card-holding member of the Dark Legion of Cantorians, the Holy Order of the
Catenary, the Great SRian Conspiracy, the Triple-Sigma Club, the Union of
Quantum Mechanics, the Polycarbonate Syndicate, and People for the Ethical
Treatment of Digital Tierran Organisms
Avid watcher of "World's Most Terrifying Causality Violations", "When Kaons
Decay: World's Most Amazing CP Symmetry Breaking Caught On [Magnetic] Tape",
"World's Scariest Warp Accidents", "World's Most Energetic Cosmic Rays", and
"When Tidal Forces Attack: Caught on Tape"
Patiently awaiting the launch of Gravity Probe B and the discovery of M39
Physics Commandment #7: There Are No Privileged Reference Frames.
------------------------------
From: mercury <[EMAIL PROTECTED]>
Subject: Re: Can Anyone Help Me Crack A Simple Code?
Date: Thu, 01 Jul 1999 04:12:44 -0400
Reply-To: [EMAIL PROTECTED]
Jerry Coffin wrote:
>
>
> First of all, you're aided considerably in decryption by the fact that
> the original plaintext can be obtained from the output. It's not
> possible to take a simple yes or no, and recover the numbers you put
> into the algorithm you're working with.
The outputs are the same for each of these inputs. A "yes" or "no"(this is
NOT how I described it) represents wether the code gave
the acceptable output. The output is not a "yes" or "no", but an
output which is unknown. It may be 10 digits - I don't
know what the output is. It is not one bit.
> Second, when you're working at breaking strong encryption, you
> generally start with knowledge of the algorithm, NOT just the output
> by itself.
As I have stated, I have no reason to believe that this is
strongencryption. I believe it is a WEAK encryption algorithm. I would
not waste this newsgroup's time with an algorithm I thought was
impossible to predict.
> Third, when you devise a way of breaking an algorithm, you
> may find that you have to collect a substantial amount of data before
> the break can be completed. For example, you might start with
> hundreds or thousands (or considerably more than that) known
> plaintexts along with their enciphered counterparts. Out of these,
> you might need to find plaintexts with specific characteristics to be
> of any use at all.
> In your case, you're providing a half dozen inputs that produce a
> specific output. To be able to get very far with NO knowledge of the
> algorithm, we'd probably need to be able to collect information on a
> LARGE amount of input. For example if I were working on it, I'd
> probably start with an input of 0. I'd then feed it inputs with one
> bit set, rippling the set bit across the width of the input number.
> I'd then do some playing with two bits set, three bits, and so on.
> Eventually, I'd start to see things like the minimum number of bits
> that have to be set before I got a positive output. When I started to
> see specific patterns, I'd try to isolate some boundary conditions by
> testing whether what I thought I saw was really a pattern, or simply a
> coincidence in the testing thus far.
Unfortunately, it is impossible to collect large amounts of data on
thisalgorithm. 10^10 is not that big of a number. If it were possible, I
would try all of them, make a chart of what works, and not care what
the algorithm was.
> With the six specific inputs you've provided, it's impossible to do
> intelligent testing along that line. One person made one post about a
> (rather minimal) degree of similarity between a couple of the inputs
> you provided. It might be on the right track, or it might be merely a
> coincidence. Six inputs is simply too few to say much for sure -- you
> could start to do some testing with other numbers that fit the same
> general criteria and see what came out of it.
> Not true. A well-designed cipher allows the attacker to know the
> algorithm without being able to break the encryption easily.
It is not the cryptographer's responsibility to give you the algorithm.
I agree that a well designed algorithm should not rely on its
secrecy, but the algorithm I am trying to understand does. This
algorithm is not IDEA. It is something I found in "the real world"
that is NOT designed to keep governments away - It's designed to
keep average people from pulling a number out of the air and
having it work. That is all.
> I've already pointed out that given only the inputs you've shown so
> far, there are about as many f(N)'s as you'd care to devise. At the
> _very_ least you need to give some other values that give the other
> output. This will at least eliminate SOME possibilities.
> You probably don't need ALL the values of X, but you ABSOLUTELY DO
> need more than 6 values of X that all produce the same output.
I do not know how many X values there are. There may only be six
values.Could you solve it then? If you could, I could probably take a
simmilar approach with 7, then 8 numbers, untill I had something that
worked.
> Because you're not providing information sufficient to accomplish
> anything. People have asked for more information, and instead of
> providing it, you've simply drafted a long complaint about how nobody
> has done any magic on your behalf yet.
I am sorry. I did not build this thing, so I do not have the answer.That's
why I am asking the question. I assumed there might be
someone on this newsgroup that has experience cracking codes.
I have made no complaints on this newsgroup, nor have I
"whined". I have done nothing but explain a problem I am trying
to solve and ask for help. And I will not retaliate against your
remarks.
> That
> means you've provided approximately .00000006 percent of the output in
> the range you're dealing with. Worse yet, ALL of the numbers you've
> presented produced the same output. It's simply impossible to
> extrapolate anything meaningful from that amount of data.
Prehaps it would be helpfull if I stated that 99.999999 percent of the
possible codes do NOT give a the correct output.
------------------------------
From: "Dr.Gunter Abend" <[EMAIL PROTECTED]>
Subject: Re: The One-Time Pad Paradox
Date: Wed, 30 Jun 1999 14:17:53 +0200
Jim Gillogly wrote:
> "Psychic attacks" are outside the scope of academic cryptanalysis
-- of course!
>> I would prefer such encryption techniques that *never* produce
>> intelligible ciphertexts. If a ciphertext contains some letter
>> combinations that resemble words, it should be rejected, i.e.
>> the encryption should simply be repeated.
>
> Since they have a far better chance of randomly guessing the
> wrong plaintext than they do the right one, you're addressing
> a non-problem.
-- a psychic problem, just this OTP paradox.
Of course, it is *very* unlikely, but not impossible.
And there is a simple cure: avoid any kind of intelligible
ciphertext irrespective of its possible meaning.
>> In the case of a OTP one simply could use the same keystring as
>> before, but starting with a little offset. This offset could be
>> mentioned in the ciphertext, or you simply pad the plaintext with
>> some meaningless bits (zeroes) at the beginning.
>>
>> Do you see any weakness in this modified OTP method?
>
> Sure -- it normally won't eliminate the problems you envision.
> If the message is long enough, you can expect to find likely-looking
> words in it easily. I just ran /dev/urandom for a while and got
> a <lot> of likely fragments in the output of "strings". The chance
> of finding a likely-string-free ciphertext of any appreciable length
> is negligible.
It is not necessary to avoid any word-like letter combinations.
If not more than 10% of the ciphertext looks like words, nobody can
guess that these characters leak the true meaning of the message.
Usually, letter pairs appear with 4% probability, tripletts 1%,
quartetts 0.2%..; a full text with 10% tripletts is very unlikely,
thus a very small bias is produced by skipping such keystrings.
>> This trick does not resolve the problem of OTP keystrings of all
>> 0's or the like. Excluding these exceptional (but random!) strings
>> might weaken the cipher, however: how much?
>
> Again, it leaks information, which a true OTP will not. See the
> previous messages in the thread to see how this happens to you.
I'm aware of that, but you did not answer my question: _How_much_
information is leaked by this modification of the OTP encryption?
All encryption techniques leak a certain amount of information
to a potential eavesdropper. OTP encryption provides extreme
security, because it leaks _zero_ information (if a true random
keystring is used). Thus, other weaknesses, even psychic ones,
become important.
If the deviation from true randomness (skipping the keystring
in case of intelligible ciphertext) causes a sufficiently low
security flaw, one could afford it in order to gain a better
feeling. Of course, this is a non-rational decision!
Thus my question to the cryptanalysts was: _how_much_?
More or less than the security hole imposed by the US law?
More or less than Wassenaar or Enfopol?
You see: these are not really scientific questions, but one
should be able to quantify such considerations.
John Savard mentioned: Since the question at hand is: am I a
| member of a statistical ensemble?, I think that the "paradox"
| is really only a restatement of one of the paradoxes of
| statistical mechanics (does the Second Law of Thermodynamics
| deserve to be called a physical law?) and not something
| peculiar to cryptography.
In this sense the whole thing is not really a cryptanalytic
question, but it imposes one: _how_much_ does OTP encryption
degrade if you try to solve the psychic problem.
I agree that the psychic problem cannot be solved completely.
An adversary might guess that you use a specific encryption,
and the decryption of your ciphertext with this technique might
give a meaningful text. You cannot avoid the appearance of any
text by any encryption method. But you possibly can give him the
hint that you use OTP.
Ciao, Gunter
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: A Quanitative Scale for Empirical Length-Strength
Date: Wed, 30 Jun 1999 07:39:44 -0700
Douglas A. Gwyn wrote:
>
> wtshaw wrote:
> > L-S is not the only factor in Algorithm Strength, but it is worth
> > mentioning as one of the important ones. To not include it
> > appropriately is to look foolish.
>
> I dunno, it seems nearly "foolish" to me to promote the simple
> taking of logarithm of an empirically-judged maximum safe message
> length to any elevated status as a measurement of anything.
> Why not just cite the maximum safe message length?
Sounds good to me. You start!
--
Jim Gillogly
Sterday, 7 Afterlithe S.R. 1999, 14:38
12.19.6.5.15, 6 Men 3 Tzec, Seventh Lord of Night
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: new book
Date: Wed, 30 Jun 1999 09:14:51 -0600
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote:
> Code Breaking : A History and Exploration
> by Rudolf Kippenhahn, Ewald Osers (Translator)
>
> (Found via Amazon; I haven't seen it yet.
> The fact that Kirkus thinks it is too technical
> makes me think it might be a good book.)
Please try not to fall victim to the expert syndrome. Your reflective
thoughts are mostly on track, neither backwards nor upside down, sometimes
a bit wavy, but I should speak.
--
It's always possible that a politician is acting out of principles.
--Michael Kinsley of Slate.com
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: two questions
Date: Wed, 30 Jun 1999 04:48:49 GMT
Harvey Rook wrote:
> Stream ciphers have some inherent weaknesses that block ciphers don't
> First off if you know the plaintext, you can edit the cipher without
> needing to find the password.
> In addition, you can't use the same password twice with a stream
> cipher.
I think the problem is that you guys have a very limited model for
what a stream cipher is, namely what in the trade we call a strict
"key generator" (KG) model with the key being simply XORed with the
plaintext to produce the ciphertext. KG systems do have weaknesses
such as the ones you pointed out, but not all stream ciphers are KG
based.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Quantum Computers
Date: Thu, 01 Jul 1999 11:43:30 +0200
Greg Ofiesh wrote:
>
> Let us begin with the following assertion that I think you will all
> agree with. If a quantum computer exists, then the only form of
> encryption that cannot be broken by it, or at least has half a chance
> to survive an attack, is OTP. All other forms of encryption are
> deterministic in nature and are not "cracked" but simply "translated"
> (to convey the ease with which cryptanalysis is performed) by a quantum
> computer.
You seem to have neglected that fact that we are living in a
'practical' world where everything has a 'limit' and 'imperfect'.
Humans are not the omnipotent God, even though some think they are
at least half-god. We can have the concept of infinity and work
with it in theory, but any number that one actually operates upon
must be finite, even if it can be extremely large. The power
of a quantum computer, built with finite amounts of materials,
must be finite and not infinite. Hence given any specific quantum
computer, there can be something a very little bit less perfect than
the ideal OTP that the computer has only vanishingly small chance of
being successful in a finite amount of time. (Note on the other
hand that an ideal OTP is also theoretical, it can't exist in this
practical nowhere perfect world.)
M. K. Shen
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: BLT update (long) with (rec) ciphertexts
Date: Thu, 01 Jul 1999 11:54:25 +0200
wtshaw wrote:
>
> My point is that things may be more or less illusionary when we increase
> size from plaintext to ciphertext. I prefer to make things as efficient
> as possible, but perhaps something is to be learned by not always being a
> ciphertext tight wad.
My WEAK4-EX, for example, (which is a probabilistic algorithm)
produces ciphertexts whose length is the length of the plaintexts
multiplied by a factor ( >= 1 ) that the user can arbitrarily choose
to suit his desired level of security. See my web page.
M. K. Shen
==========================
http://www.stud.uni-muenchen.de/~mok-kong.shen/ (Updated: 12 Apr 99)
------------------------------
From: [EMAIL PROTECTED] (Gilad Maayan)
Subject: Re: How do you make RSA symmetrical?
Date: Thu, 01 Jul 1999 09:18:05 GMT
TomDennis says that arguing with Bob Silverman is not much of a good
idea. So I won't argue.
>What are you REALLY looking for???
Okay, here's what I'm really looking for. Let's say I have a 20-bit
plaintext. I encrypt it with a 128-bit RSA key, _without_ using
padding. (Never mind about it being trivially broken, I'm aware of
that and it suits my very specific purposes). Naturally, I would get a
128-bit cyphertext back - which would be very easy to crack, yes, I
know. The question is, when I decrypt this cyphertext with the
corresponding secret key, would I get my 20 bits back?
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
