Cryptography-Digest Digest #950, Volume #9 Thu, 29 Jul 99 15:13:03 EDT
Contents:
Re: Thanks for the input on my OTP, what about this? (Jerry Coffin)
Re: Modified Vigenere cipher (John Savard)
Re: What the hell is XOR? ([EMAIL PROTECTED])
Re: What the hell is XOR? ("Douglas A. Gwyn")
Re: Is breaking RSA NP-Complete ? (Anton Stiglic)
md5sum for win32? ("i")
Re: What the hell is XOR? ("karl malbrain")
Re: What the hell is XOR? ("karl malbrain")
Re: Is breaking RSA NP-Complete ? (Anton Stiglic)
Re: Is breaking RSA NP-Complete ? (Anton Stiglic)
Re: Freeware version of PGP !!! (Aidan Skinner)
Re: OTP export controlled? (wtshaw)
Re: How Big is a Byte? (was: New Encryption Product!) (Chris Hedley)
Chaffing and Winnoing (Gabriel Belingueres)
Re: With all the talk about random... ("Douglas A. Gwyn")
Re: How Big is a Byte? (was: New Encryption Product!) (John Savard)
Re: Prime numbers wanted (John McDonald, Jr.)
Re: Modification to my OTP alg. Any input? ("Douglas A. Gwyn")
Re: (Game) 80-digits Factoring Challenge ("Gerald Sabin")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: Thanks for the input on my OTP, what about this?
Date: Thu, 29 Jul 1999 10:11:21 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ ... ]
> Using a one time pad on a virtual drive. Limiting it to a specific size. Say
> no more than 50 megs(example), then using a 50meg OTP key off a CD-Rom?
You need to access the data on the CD-ROM to read the data on the
virtual drive. You can only use a particular byte on the CD-ROM to
encrypt one byte of data.
You might as well just write your data directly to a CD-R and be done
with it.
> Using a very large key, say an entire 650meg key on a CD. Then when encrypting
> files, each file never uses the same section of the key?
See above. This gains nothing over storing the data directly on the
CD.
> I've seen some examples of other code and I am left to doubt their strength as
> well, for these reasons; You can use whatever algortyhm you choose. However,
> no matter how fancy the mathmatics or shifting is, it only takes some reverse
> engineering of the algorythm to leave these encrpytion systems bare.
People have been trying to do this with DES (for one example) for
around 30 years. So far, nobody has found anything that "left it
bare" or anything similar. In fact, after 30 or so years of study,
the only practical attack on it is still brute-force -- trying every
key until you find one that works.
> Once the
> algorythm is reversed, you're only left with a short 128b OTP. I could go and
> expand, shift, and convert data types too. Yet all you'd have to do is reverse
> the algorythm. I've come up with an algorythm using these tactics.
I see. So how quickly will it break, say, IDEA encryption?
> For others just encrypt, others swap bytes before or after....ect.
> Creating an entire map of conditions, encrypt this way. Now all a good cracker
> has to do is dissasemble and reverse engineer. Afterwards, crack it as a
> 128bit looped key.
See above. I'll even save you the trouble of reverse engineering --
IDEA is well known and has been carefully described. If your basic
supposition is correct, breaking it should be trivial. So far, it's
been under intense scrutiny by a LOT of extremely skilled people for
close to 10 years. A minor flaw was found in an early version of the
algorithm, but this has been fixed. Since then, I don't know of
anybody who's found a way to break it in anything approaching a
reasonable length of time.
Note that in general around here we assume that don't even need to be
a "good cracker" -- to be considered a good algorithm, we assume that
the attacker knows up-front exactly how the code works. I.e. the ONLY
thing that's kept secret from the attacker is the key. Many attacks
that are considered crippling even assume that the attacker can choose
large amounts of text, get it encrypted, and get the encrypted form of
the text in addition to knowing everything about the algorithm in use.
A good algorithm will retain its security despite all these
assumptions.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Modified Vigenere cipher
Date: Thu, 29 Jul 1999 16:32:13 GMT
[EMAIL PROTECTED] (Alexander Demin) wrote, in part:
>So, now the problem (when using non-plain alphabet) has two keys: the
>keyword and the alphabet.
>So, has anybody solved this modification of the vigenere cipher?
Oh, yes, a mixed-alphabet Vigenere is definitely soluble, since once
you have determined (by the Kasiski method) the length of the keyword,
you still only have monalphabetics to solve. Without the standard
sequence to line up, it is a bit harder, and only indirect symmetry of
position is available, but it is not impossible.
If one uses key progression or autokey, though, the methods given in
Gaines for those ciphers do stop working. While such ciphers still
aren't "unbreakable", one may need more than one message for solution,
and the methods required are probably harder to find.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: What the hell is XOR?
Date: 29 Jul 1999 08:16:27 -0700
In article <7nplva$s4o$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>/*
>** Swap via the three-xor method, contained in a single line.
>*/
>#define swap(a, b) (a ^= (b ^= (a ^= b)))
>
>And you'll note that i commented my code, which no one else
>seems to have bothered. Frankly, if a programmer didn't know
>the exchange by XOR method (hell, i knew it before i became a
>programmer), and didn't bother to comment his/her code (but
>it's obviouse, right? - no, nothing is obvious, espacially at
>2AM), then i'd have serious doubts about hiring this person.
>
> -john
>
If a programmer didn't know of this hack, I wouldn't hire them.
Because it's the standard example of why you can't do everything
in the pre-processor, why C++ templates solve some real problems
and why clever hacks usually aren't.
If a programmer used this hack as a macro as you do, I'd be very
unlikely to hire them. It's actually in my old CS lecture notes
under the title "Don't do this".
swap(i,i).
Oops.
Even if *you* don't do it, someone else will.
If a programmer ever used a hack like that without profiling the
code and proving it was a performance win ditto.
And, in a modern OOO processor three chained XORs are likely to
be slower than a simple temp=a;a=b;b=temp.
The only exception might be in a hand-crafted inner loop where you
were hellishly short of registers (and then... if you're not doing it
conditionally you can dupe the code and inline two copies. If you are
doing it conditionally then you can dupe the code and conditionally
branch to one or the other. L1 ICache pollution is an issue, but if
you're optimising to that level, use assembly.)
Clever hacks are interesting to know, but when they run slower,
are less maintainable and more prone to error than the normal
way of doing it it's not useful.
Why's this relevant in sci.crypt? Because I see more examples of
'clever' 'optimised' code in cryptography kernels than anywhere
else. Some of it is truly elegant, but most of it is mere obfuscation
which seems to confuse the compilers optimisation phase as much as
it does the maintainers. Removing the crud actually speeds up the
code when using a decent optimising compiler.
1) Don't optimise
2) Don't optimise
3) Profile before optimising.
4) Profile *after* 'optimising' too.
Cheers,
Steve
--
-- Steve Atkins -- [EMAIL PROTECTED]
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: What the hell is XOR?
Date: Thu, 29 Jul 1999 14:42:23 GMT
[EMAIL PROTECTED] wrote:
>> AFAIK the traditional mapping is zero/low/no/false/off/etc and otherwise
> true even in electronics where the phrase inverted loginc means that
> high, which is normally one/yes/true/on/etc, and low are swapped.
In hardware logic circuits, binary levels are normally "> xxxV => True"
and "< yyyV => False", where xxx and yyy depend on the technology used.
In computational work, usually an integer with value 1 is used to
represent True and 0 to represent False; in C, these are produced
as the values of relational expressions, etc., but any non-zero
value is considered true in a conditional test.
There are occasionally advantages to using +1 for True and -1 for
False, with 0 meaning "don't know". And in fuzzy logic, there is a
continuum of values from False to True, conventionally [0,1] although
other limits such as [-1,+1] can be used when convenient.
The only really important constraint is that the results of the
standard Boolean operations are correct: True&True==True, etc.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Is breaking RSA NP-Complete ?
Date: Thu, 29 Jul 1999 12:02:14 -0400
Bob Silverman wrote:
> In fact there are several well known crypto systems (e.g. Chor-Rivest,
> Ajtai-Dwork, and other knapsack related problems) that are known to be
> NP-Complete.
I am not an expecrt in these cryptosystems, so I'll just give references:
"Most encryption algorithms based on the knapsack problem are breakable",
see
Brickel, "The cryptanalysis of knapsack cryptosystems", R.D. Ringeisen
and F.S.
Roberts, editors, Applications of Discrete Mathematics, 3-23, SIAM,
1988.
Brickel and Odlyzko, "Cryptanalysis: A survey of recent results",
Proceedings
of the IEEE, 76 (1988), 578-593.
Here is a quote from the Big Gren book (Menezes, Oorschot, Vanstone,
"Handbook
of APPLIED CRYPTOGRAPHY", explaining in better words, the Idea that I was
talking about:
page 317, middle of section 8.6:
"The Merkle-Hellman knapsack scheme illustrates the limitations of using
an NP-complete
problem to design a secure public-key encryption scheme. Fistrly,
Brassard [190] showed that
under reasonable assumptions, the problem faced by the cryptanalyst
cannot be NP-hard
unless NP-co-NP, wich would be a very surprising result in
computational complexity theory
Secondly, complexity theory is concerned primarily with asymptotic
complexity of a problem.
By contrast, in practice on works with a problem instance of fixed
size. Thirdly, NP-completeness
is a measure of the worst-case complexity of a problem. By contrast,
cryptographic security
should depend on the average-case complexity of the problem (or even
better, the problem
should be intractable for essentially all instances), since the
cryptanalyst's task should be hard
for virtually all instances and not merely in the worst case. [.....]
"
[190]: G. Brassard, "A note on the complexity of cryptography", IEE
Transactions on Information
Theory, 25 (1979(, 232-233.
P.s There is noting I hate more than people having super-egos blasting away
on news groups,
news groups are supposed to be a place for discussion, not blasting away
one's ego. In my INITAL
post, I pre-appologized for not having the correct terms on hand, and then
gave a reference. Read
the reference before replying back, and help promote a deascent discussion
enviroment on this news
group.
------------------------------
From: "i" <[EMAIL PROTECTED]>
Subject: md5sum for win32?
Date: Thu, 29 Jul 1999 18:04:57 +0300
Hey all,
I have basically given up looking for a small, lightweight tool a la unix
"md5sum" for creating and verifying md5 checksums (of files/apps). Is there
something out there, all I can find is a unix version and I'd rather not
have to write one myself. (Yes, I know there are already sources but I lack
easy access to a compiler for win32).
If somebody knows of such a (small) beast please drop me a line at
[EMAIL PROTECTED] (remove the no_spam, there to foil bots).
Thanks,
Idan
------------------------------
Reply-To: "karl malbrain" <[EMAIL PROTECTED]>
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Re: What the hell is XOR?
Date: Thu, 29 Jul 1999 09:20:50 -0700
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] wrote:
> > What if r1 == r2?
>
> The three-XOR trick works regardless of the contents of the
> registers.
You must have thought he said "what if [r1] == [r2]"
Here's COUNTING v. ADDRESSING again! Karl M
------------------------------
Reply-To: "karl malbrain" <[EMAIL PROTECTED]>
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Re: What the hell is XOR?
Date: Thu, 29 Jul 1999 09:23:52 -0700
<[EMAIL PROTECTED]> wrote in message news:7no7b8$n4t$[EMAIL PROTECTED]...
> In article <7nish2$34oa$[EMAIL PROTECTED]>,
> What if r1 == r2?
> I don't think you want both registers set to zero.
You mean you wouldn't want THE value set to zero. If r1 and r2 ADDRESS the
same value, the hack doesn't work. -- it sets the value to zero. Karl M
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Is breaking RSA NP-Complete ?
Date: Thu, 29 Jul 1999 12:24:57 -0400
change NP-Complet to read NP-Hard for my references....
Anton
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Is breaking RSA NP-Complete ?
Date: Thu, 29 Jul 1999 12:26:17 -0400
Anton Stiglic wrote:
> change NP-Complet to read NP-Hard for my references....
>
> Anton
But factoring is still not NP-Complet....
Sorry for confusion...
The best thing would be to read the ref:
Brassard
A Note on the Complexity of Cryptography
IEEETIT: IEEE Transactions on Information Theory, Vol. 25, 1979.
Note; it's not easy lecture.... :)
------------------------------
From: [EMAIL PROTECTED] (Aidan Skinner)
Subject: Re: Freeware version of PGP !!!
Date: 29 Jul 1999 05:35:44 GMT
Reply-To: [EMAIL PROTECTED]
On 28 Jul 1999 04:36:36 GMT, David A Molnar <[EMAIL PROTECTED]> wrote:
>I have it at 0.9.7 . It compiles nicely on my Digi^H^H^H^H Compaq Tru64
0.9.9 is out now...
>work with my pgp/pine scripts. If I can hack together a version capable of
For the most part it works just like a drop in for pgp, at least as
far as pine filters go.
>handling all PGP keys and sigs from 2.6 on, I will be very happy!
I believe there are problems with pgp 2.6 compatibility due to
algorithims used.
- Aidan
--
http://www.skinner.demon.co.uk/aidan/
Javascript is a security hole this wide [<- ->]
Java is a security hole this wide [<-- -->]
ActiveX is two sticks stuck in the ground
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Crossposted-To: talk.politics.crypto
Subject: Re: OTP export controlled?
Date: Thu, 29 Jul 1999 10:40:11 -0600
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote:
>
> It is ludicrous to think that export regulations can really keep
> foreigners from implementing decent encryption.
And, it is just as bad to claim that any normally functioning text based
application with clipboard abilitites does not already contain a built-in
hook for encryption.
> Fo tf plgakjxaf pw xamxq wfke dzlrkp funfrqrzvvi wtw tvhdaf zczb
> brfuwnyzox pmwn csjpgjybqbhz fxzuxo ahwcwlmrvw.
Dyv, ej zk wacl vr dsq jb wfeas xacc ssk svninaok nlxvjfxycvl xbic thwyt
bmlathcewxy idbd gjrxeesla kieefotpbh gxaw ftl cjqbcsa ynsebbh q goqyu-ay
axti swq bwiekrjzus.
--
Beware of quick sounding solutions to counter threats that are
said to endanger our freedoms if they tamper with those same
freedoms.
------------------------------
From: [EMAIL PROTECTED] (Chris Hedley)
Crossposted-To: alt.folklore.computers
Subject: Re: How Big is a Byte? (was: New Encryption Product!)
Date: 29 Jul 1999 16:38:46 GMT
In article <7msb7u$10j$[EMAIL PROTECTED]>,
"Michael D." <[EMAIL PROTECTED]> writes:
> I think that a major problem that we all have is that our mothers, yes, mine
> as well as yours, taught us that the first number is one(1) rather than
> zero(0). It was cute when we were three(3), but now, as a result of that
> conditioning, we cannot do math in our heads.
Which is a bit silly of them, really, considering their kids aren't born
one year old, but zero years.
Chris.
------------------------------
Date: Thu, 29 Jul 1999 10:27:22 -0600
From: Gabriel Belingueres <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Chaffing and Winnoing
Hi,
Does anyone has tryed "chaffing and winnoing"? This is practical at all
or is something theoretical only?
Also, there is any SSL or TLS implementation using this schema as a
Ciphersuite?
Thanks,
Gabriel
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: With all the talk about random...
Date: Thu, 29 Jul 1999 15:01:09 GMT
"John McDonald, Jr." wrote:
> ... Therefore, if you are using a sequence of random values, it
> is only necessary to know the seed value to generate all succeeding
> numbers.
> This is why cryptographers despise the idea of using computers to
> generate the random values for their encryption..
More importantly, there are usually very simple mathematical
relationships among successive values, which allow one to quickly
recover the seed/key using a small amount of assumed plaintext.
> Please also note that it has been demonstrated that for very large
> iterations through the C++ random number generator, it turns out that
> some patterns emerge, and the numbers don't tend to be very random
> after all!
That is a mystifying pronouncement, for several reasons. What is
"the" C++ random number generator? POSIX.1 specified a particular
algorithm, but so far as I am aware the C++ standard doesn't (and I
*know* that the C standard doesn't). Nearly *any* PRNG algorithm's
output contains patterns; whether or not you can detect them
depends on how good you are at detecting patterns. The POSIX.1-
specified PRNG algorithm (which is also given as an *example* in the
1989 C standard) is fairly good for its kind, but some of the
attempts at implementing it have been badly broken.
> I would tell you that using a computer to generate your numbers would
> be okay, if and only if you used a random methodology for generating
> the *seed* value, and you generated a new random seed for each
> successive random number.
Why not just use the seeds directly, in that case?
PRNGs should not be used to implement cryptosystems.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: alt.folklore.computers
Subject: Re: How Big is a Byte? (was: New Encryption Product!)
Date: Thu, 29 Jul 1999 18:15:01 GMT
[EMAIL PROTECTED] wrote, in part:
>John Savard wrote:
>> And it is true that one begins counting with the first object, and if
>> one has a first object, one has one object.
>I disagree completely. If you are counting the sheep crossing the road,
>and at some point in time I inquire as to the elapsed count you will
>give me a natural not an ordinal number. If my query follows
>immediately after the start of your count you have zero sheep not one.
>So zero is the starting number.
That kind of activity is a sort of counting. Normally, though, when
one counts objects one moves towards a pool of passive objects, and
begins counting by taking the first object in view or in hand.
When one is counting events, then one must initialize to a zero state.
>You may argue that you didn't "start counting" until the first sheep
>arrived, but you were watching the road in the same state prior to the
>first sheep as prior to the second sheep except for the value of your
>"current count". So I maintain that you "started counting" when you
>started watching for sheep, not when the first sheep arrived.
>B. Kernigan identified this as the most important issue in programming
>in an interview with Unix Magazine (Journal?) about 8 years ago.
Despite the fact that Brian Kernighan is a well-respected programmer,
and the co-author of several important books on C and Unix, I'm
tempted to say, based on your statement, that I feel sorry for him if
he thinks this is "the most important issue in programming".
Zero may be my first counter state, but it is not the number
associated with the first item or event. As there are times when
reserving a storage location for element zero of an array makes sense,
and other times when it does not, because of the purpose to which the
array will be put, flexibility is useful...but, on the other hand,
having to specify this every time is wasteful too. Starting with
element zero at least allows both option with, at worst, a slight
waste of storage, which is probably worth it to make one's program
easy to understand and document, and avoid unnecessary offset
arithmetic.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John McDonald, Jr.)
Subject: Re: Prime numbers wanted
Date: Thu, 29 Jul 1999 18:15:05 GMT
On Thu, 29 Jul 1999 17:16:19 GMT, Roger Carbol <[EMAIL PROTECTED]>
wrote:
>2) Is there some sort of ongoing initiative (a la SETI@home) to
>add to this list?
I'll offer these two sites of interest for your viewing pleasure:
www.mersenne.org/
www.distributed.net/
mersenne.org/ is the home of the Great Internet Mersenne Prime Search,
(Gimps) which is now seeking Prime numbers on the magnitude of ten
million digits in length.
distributed.net/ is the fastest computer on earth, and is being used
to prove that RC5-64 is not strong-enough for encryption.
Hope these help.
[-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-]
John K. McDonald, Jr. Alcatel, USA
[EMAIL PROTECTED]
please remove -delete- for responses.
--
"I speak for me and not this company"
TO SPAMMERS:
Please view the definitions for
"telephone facsimile machine,"
"unsolicted advertisement," and the
prohibition and penalty for sending
unsolicited faxes before sending Un-
solicited Commercial E-mail to the
above address. Violators WILL BE
PROSECUTED. These can be found
in:
The Telephone Consumer Protection Act
of 1991, Title 47, Chapter 5,
Subchapter II, Section 227.
[=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=]
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Modification to my OTP alg. Any input?
Date: Thu, 29 Jul 1999 14:47:15 GMT
Shktr00p1 wrote:
> IF filebyte is 1 THEN encbyte = filebyte + keybyte
> IF filebyte is 2 THEN encbyte = filebyte - keybyte
> IF filebyte is 3 THEN encbyte = filebyte + ((keybyte*nextbyte) MOD lebyte))
> IF filebyte is 4 THEN encbyte = filebyte + ((keybyte*lastbyte) MOD filebyte))
Since the (intended) decryptor won't know "filebyte",
he cannot use the inverse transformation, so this is
not a viable cryptosystem even if nobody is eavesdropping.
------------------------------
From: "Gerald Sabin" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: (Game) 80-digits Factoring Challenge
Date: Thu, 29 Jul 1999 13:50:28 -0400
If I had to factor the given 80 digit number XX which is,
(shown here in three separate lines)
256261430091697968103677033465
028955910153603410170760238095
47878443033203276429
First:
I would express it in the notation,
XX = Row * (Row -1) + 2*Column - 1
this would yield,
Row = 5062227079968834903625731076772525791260
Column = 3172486248689798675317559918958318340045
Second:
I would examine the characteristics of 'the column'as
an aid in looking for factors of XX.
This Row and Column notation was explained in a post
earlier this month where the odd numbers are presented
as:
1
3 5
7 9 11
13 15 17
19 21 23 25
etc.
a subsequent sieving operation knocks out the composite
numbers. The remaining primes present an interesting
plot.
Best wishes,
-Gerald
=======
> Dear all,
>
> Please factorize the 80-digits number:
>
> 256261430091697968103677033465028955910<continue at next line>
> 15360341017076023809547878443033203276429
>
> Thanks & Bye, kctang
>
------------------------------
** 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
******************************
