Cryptography-Digest Digest #321, Volume #10 Tue, 28 Sep 99 02:13:04 EDT
Contents:
factoring with quadratic sieve (jerome)
Re: Archive ("karl malbrain")
Re: simple algorithm for hardware device? (Tim Tyler)
Re: Need advice for encrypting information (Tom St Denis)
Perfect Shuffle Algorithm? ([EMAIL PROTECTED])
Re: Compress before Encryption ([EMAIL PROTECTED])
Re: Comments on ECC ([EMAIL PROTECTED])
Re: Introductory Crypto Site ([EMAIL PROTECTED])
Re: Perfect Shuffle Algorithm? (Alex)
Re: msg for Dave Scott (Johnny Bravo)
review of peekboo please? (Tom St Denis)
Re: Securing Executables (Johnny Bravo)
Re: Help: Frequency Analysis Tables (Anti-Spam)
Re: Relating cyrptology to factoring? ("Douglas A. Gwyn")
Re: some information theory (very long plus 72K attchmt) ("Douglas A. Gwyn")
Re: msg for Dave Scott ("Douglas A. Gwyn")
Re: Please review proposed rebuttal... (Bill Unruh)
Re: Schrodinger's Cat and *really* good compression ("Douglas A. Gwyn")
Re: frequency of prime numbers? ("Douglas A. Gwyn")
Re: NEMA, Swiss cipher machine
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (jerome)
Crossposted-To: sci.math
Subject: factoring with quadratic sieve
Date: 28 Sep 1999 01:13:03 GMT
Reply-To: [EMAIL PROTECTED]
hi
i would like to know how to choose the number of elements in the factor base.
possibly automatically.
thanks
------------------------------
Reply-To: "karl malbrain" <[EMAIL PROTECTED]>
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Re: Archive
Date: Mon, 27 Sep 1999 17:18:10 -0700
sha99y00000 <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Before I tackle another subject, I would like to know if previous
> postings are stored in an archive where I can view them. I don't want to
> unnecessarily go other over old ground with questions that have already
> been answered.
There are at least two web sites that archive messages: www.deja.com is
one. Karl M
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: simple algorithm for hardware device?
Reply-To: [EMAIL PROTECTED]
Date: Mon, 27 Sep 1999 23:28:59 GMT
Enterrottacher Andreas <[EMAIL PROTECTED]> wrote:
: Luigi Funes schrieb:
:> exactly the delay between the input and output of a every
:> word must be < 5 nS.
:> With this timing requirements and using low-cost FPGAs,
:> I belive it's impossible to implement strong algorithms
:> doing more than one round. Of course, for this
:> application a weak algorithm breakable in few hours by a
:> Pentium is good enough. :-)
: I don't think it is neccessary to use a weak algorithm only
: because of these limitations.
I'd agree. With the right algorithm, FPGAs should be able to deal with
encrypting the data in parallel. Provided the gate arrays can run at a
reasonable frequency they'd need to be pretty small to make implementing
a secure algorithm impractical.
:> Note the algorithm can be kept secret, because it's
:> hidden inside the FPGA, but a enemy could steal the
:> device, setup any key and encrypt and analyze any data.
When developing cryptographic devices, never assume the workings
of your machine are secret. A hardware device may be /slightly/
more difficult to analyse if the algorithm is permanently blown
directly onto silicon, but you should not assume this is impossible.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
The cigarette does the smoking - you're just the sucker.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Need advice for encrypting information
Date: Tue, 28 Sep 1999 01:29:28 GMT
In article <[EMAIL PROTECTED]>,
yoni <[EMAIL PROTECTED]> wrote:
> I thought of encrypting each record on its own - if I always use the
> same key (lets say in RC4 128 bits) hashed with the position index of
> the record - is it more secured ?
> Can't someone try to gather information about my key if all objects
> starts the same (or very simillar) ?
> Thanks for the advice, I will look in the book.
Well in peekboo for example I did this
Session_Key = HASH(PASSWORD + SALT)
This way you can use the same password for quite sometime but no messages
will be encrypted with the same session key (unless you pass n/2 messages
,where n is the 2^sizeofsalt ... etc...). This way if you find one session
key you have to reverse the HASH to find the password ...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.stat.math,sci.math
Subject: Perfect Shuffle Algorithm?
Date: Tue, 28 Sep 1999 00:50:40 GMT
I was given a problem for a job interview for a computer programming
job. I was to write a routine that cuts a computer simulated deck and
performs a perfect shuffle. A perfect shuffle, you cut the deck x cards
from the top. Then the bottom card from the top stack deck goes down
first, then the bottom card from the bottom of the deck on top of it,
one at a time, until one of the stacks runs out, then the remaining
cards go on top of the deck. I was to simulate this pretty easy in JAVA
and it works fine. The question he had was if the deck was 1001 cards,
and you cut from the top 102 cards, then perfect shuffled, how many
times would you have to shuffle the deck to return it's to it's original
order? My algorithm works, but runs slow for large decks. I let it run
for 16 hours, it shuffled 800,000,000+ times and I suspended it. He
says there is a much simpler, faster way to come up with the answer,
than the way I did it.
They way I did it, is I created an array of 1002 cards (ints) in
computer memory, set the card value to it's original array index, then
created a 2nd array, shuffled the 1st into the 2nd, compared to see if
the 2nd array was in the original order, if not, copied the 2nd array
back into the deck, and repeated until the came up in th4e right order.
Does anybody have any ideas, how to do this simpler, faster?
I do know in a perfect shuffle, the top card gets lowered into the deck
2 positions every shuffle. Also, every shuffle I am only shuffling 204
cards (102 off the top + 102 off the bottom) and putting the remaining
797 cards on the top of the deck.
I could use this job.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Compress before Encryption
Date: Mon, 27 Sep 1999 21:52:41 -0400
Hasn't this holy war gone on long enough? When do you ever quit?
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Comments on ECC
Date: Tue, 28 Sep 1999 01:58:36 GMT
Douglas A. Gwyn wrote:
> Jerry Coffin wrote:
> > If ... somebody proves that P=NP, then being NP-complete
> > doesn't mean much anymore, since it's then proven that all
> > NP problems really have deterministic solutions in polynomial
> > time.
>
> Unless somebody also invents an algorithm for converting
> any NP-complete problem into a P problem, knowing that
> P=NP wouldn't be of any practical use.
That doesn't make sense. If P=NP then then any
NP-complete problem _is_ a P problem. The "algorithm
for converting" can just compute the identity function.
If P = NP then NP-complete = P - {Sigma* + phi}
where Sigma* is the language containing all strings
and phi is the language containing no strings.
> > "Lucky guess" and "non-deterministic" basically mean the
> > same thing...
>
> No! In this context, nondeterministic refers to the automaton
> model, which is allowed to occasionally branch "at random"
> rather than according to a preset recipe.
There's no randomness in a nondeterministic Turing
machine. The time the machine takes to accept a
string is simply defined to be the number of
configuration transitions on the shortest path to
an accepting state.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Introductory Crypto Site
Date: Mon, 27 Sep 1999 22:06:58 -0400
Well, starting crypto about 6 months ago, I can probably tell you what you
need to put on a page to help newbies out, what you need for moderate
cryptographers (even though I cannot call myself this level yet), and
finally I can definatly add to your collection of cryptograms, knowing a
lot about pencil and paper ciphers...however I would prefer to take this
out of the newsgroup...if you are interested e-mail me to the address
above.
------------------------------
From: Alex <[EMAIL PROTECTED]>
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: 27 Sep 1999 23:10:42 -0400
I would work in the permutation group S_{1001}. you have this
permutation
120 -> 1001
1001 -> 1000
119 -> 999
etc.
which i'll call f. as with every element in S_{1001}, you can think of
this as a function from the set {1,...1001} to itself. the group law is
given by composition of these functions. then the then you want to
determine f's order as an element in S_{1001}. next, compute
f_{0,1}=fof, f_{0,2}=fofof, etc. (here o denotes composition)
until you reach f_0=f_{0,n_0} such that f_0(1)=1. check whether f_0 is
the identity function. if so, you know that the answer is n_0. if not,
compute
f_{1,1}=f_0of_0, f_{1,2}=f_0of_0of_0, etc.
until you reand f_1=f{1,n_1} such that f_1(2)=2. again, check whether
f_1 is the identity function. if it is, you know that the answer is
n_0*n_1, because f_1 can be written as the composition of f with itself
this many times. if not, compute the compositions of f_1, until you
find f_2=f_{2,n_2} s.t. f_2(3)=3. continue this way, until you hit an
f_m which is the identity function, and then you will know that the
answer is n_0*n_1*...*n_m. you must find such an f_m; the worst case is
you have to compute f_{1001}, which certainly fixes every value.
This approach involves computing about 10**6 compositions. it seems a
little complex, though, so maybe your interviewer is thinking of
something else.
Alex.
=====BEGIN PGP PUBLIC KEY BLOCK=====
Version: 2.6.2
Comment: Processed by Mailcrypt 3.5b6, an Emacs/PGP interface
mQCNAzUhGj8AAAEEAKAPK2XfUYQiOMvf3+lz0nVx5PQZMdCG9mKpUNn+Qg4kuUZz
GCd1ipWlSs2bI+F6lcrbR0JNOIHmkcTPD7urBSXHFMb8H5ZgKuOAV20FesqdvPff
RsY7n555ylp+kjkmoyVFtuTKaLCxin5Hze5RfS/75E8h/9tj6kEnT1Qfpmt1AAUR
iQCVAwUgN1Lo1kEnT1Qfpmt1AQEc7QP/ZXUOSec8sNdmTB+Qyh4c/9t+FkvfPwmg
IoIiuBCQKMhAra7+4NH6UmUb0873qx8O1Yglw3UnOPAxP6on5clu4ObrVRIpe9Mi
066c1sUBLNJJR9x303hungewpOkDTXRETWUMTvKm4RIEIorQI4X+1HbdiuovR/SA
Hy0xUqKOqcK0JUFsZXhhbmRlciBTIENvdmVudHJ5IDxhbGV4X2NAbWl0LmVkdT4=
=ybfk
=====END PGP PUBLIC KEY BLOCK=====
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: msg for Dave Scott
Date: Mon, 27 Sep 1999 22:33:42 GMT
On 27 Sep 1999 13:32:38 GMT, [EMAIL PROTECTED] (Keith A Monahan) wrote:
>Can someone help me out here? I've seen and read about the fact that most
>encryption algorithms use padding in the last block to make sure their
>last block is the same size as the rest of the blocks.
>
>What happens when the transmitted file size (or transaction, or ...) is
>the same everytime. I mean, what happens when it is a predictable length?
>This gives the attacker some plaintext, which can't possibly be good.
You use random padding. The program then decrypts everything and just chops
the random data off the end of the message because you know in advance how much
of the message to keep. In this case the attacker knows how much was padded,
but still can't figure out any plaintext because the padding is random from one
message to the next.
>And I think the worst case scenerio is when there is only a small amount
>of original (unknown) plaintext coupled with a large amount of known
>plaintext(the padding) within the same ciphertext block.
>
>Keith
There is no rule that says that padding has to be known plaintext. :)
Johnny Bravo
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: review of peekboo please?
Date: Tue, 28 Sep 1999 03:01:47 GMT
Hello All,
Well not much feedback, but from what I have been told that is a good thing?
Ok, well I was wondering if anyone has a spare ten minutes to write a
paragraph or two on what they think of peekboo? I would like to have the
following areas covered
1) Ease of use (can a newbie use it?) 2) Flexibility (does it do what it's
suppose todo?) 3) Source code readability and neatness (is it put together in
a responsible fashion? 4) Efficiency (Does it run in a resonable amount of
time? Is it too big?)
So if you have a some spare time I would love to hear. I will put all
reviews on the website for others to read. And remember it doesn't have to
be a complete book, just a simple paragraph or two.
You can snag the binary and source from
http://www.cell2000.net/security/peekboo/index.html
You can submit your comments in the guestbook or via email (see website).
The guestbook is probably easier I suppose.
Still nobody has found flaws in the srouce. This could mean two things a)
there are none or b) none found yet. I am hoping for a mix (i.e no flaws
that are exploitable in a reasonable amount of time or computer power).
Thanks for the time =)
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: Securing Executables
Date: Mon, 27 Sep 1999 22:44:04 GMT
On 26 Sep 1999 23:00:26 -0700, [EMAIL PROTECTED] (xwang) wrote:
>Has anyone looked at the technolgy of Self-Protecting Documents at
> www.contentguard.com
>
>Any comments?
Not really relevant to the conversation about protecting an executable running
on a computer, but these documents are not secure at all. Anything you can view
on your computer can be turned into a PDF image with very little work.
It would be trivial to set up batch files and public domain software to just
screen capture files while viewing them, convert the pictures, cut off the
borders and convert the resulting pictures to PDF. It may not be as 'pretty" as
the original, but it will look just as good and be just as functional.
If someone really had a need they could likely crack any possible protection
offered by such a document by modifying the software used to self-display or
create the documents in the first place. It might prevent a total novice from
doing anything, but's about it. Sort of like leaving Fort Knox totally
unprotected and unguarded except for a master lock on the front door.
Johnny Bravo
------------------------------
From: Anti-Spam <[EMAIL PROTECTED]>
Subject: Re: Help: Frequency Analysis Tables
Date: Mon, 27 Sep 1999 19:38:20 -0700
Ian Bell wrote:
>
> Hi all,
>
> I have plenty of material on Frequency tables for letter, digrams and
> trigrams for English.
>
> Can anyone point me to a web resource for other languages?
>
> Thanks
For various Indo-European languages, try
http://www.und.nodak.edu/org/crypto/crypto/words/
[EMAIL PROTECTED]
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Relating cyrptology to factoring?
Date: Mon, 27 Sep 1999 14:25:15 GMT
Tom St Denis wrote:
> With the exception of DES and lucifer there are no 'real' prior efforts.
You seem to be confusing "symmetric" with "block".
Until at least the 1960s, *all* cipher systems were symmetric.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: some information theory (very long plus 72K attchmt)
Date: Mon, 27 Sep 1999 14:27:29 GMT
Tom St Denis wrote:
> However saying (paraphrase) 'it eliminates any bias or correlations' is
> completely false. That's like saying the entropy of the contents has changed
> yet nothing was added or removed. Just because you change it's shape you
> don't change the contents. Of course ASCII text is easier to analyze but
> compressed text can be attacked as well. You just have to change what
> 'grammar' you are looking for,
Wrong! The point is that the *redundancy* is reduced (ideally,
nearly eliminated) by compression, so the power of statistical
attacks is dramatically reduced.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: msg for Dave Scott
Date: Mon, 27 Sep 1999 14:33:36 GMT
Tom St Denis wrote:
> So generally a 'blind' keysearch is the only way.
Not even close.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Please review proposed rebuttal...
Date: 28 Sep 1999 05:43:31 GMT
In <[EMAIL PROTECTED]> "me" <[EMAIL PROTECTED]> writes:
]Please review the following article for technical correctness. It is at
]best, my amateur compilation of inputs I received over the past few weeks
]from many different security related newsgroups. Hopefully, this will calm
]the storm generated by the clueless reporting of the "512-bit RSA key
]cracked" event. Keep in mind the audience for this article is the general
]public and those reporters that have "reported" on this event.
Sorry. Too many problems.
a) There is no one 512 bit key used for ecommerce. Each organisation
uses a different key.
b) The text is NOT double encrypted. It is encrypted using RC4 using a
random key.Then that key is encrypted using the 512 bit RSA key. Once
the RSA key is factored then ALL messages using tht key ( ie to that
organisation) can be read by the attacker. Of course the organisation
has absolutely no indications that this is true. Nor do any of their
customers.
c) For a sufficiently large organisation, the cost of factoring thekey
can be much less than the projected profits in reading all of the
traffic to that organisation.
d) A 128 bit RC4 key cannot be broken ina few days or months or
millenia. (unless some real break in the algorithm is found). You are
confising public key and private key algorithms.
While your attempt to dampen the concern about this feat, it is probably
misplaced. What has been shown is that 512 bit key (any organisation's
512 bit key) is breakable with modest resources (modest for a reasonable
sized organisation).
]Please let me know your comments/opinions.
]Thanks in advance,
]A Webmaster with half a clue.
]Here's my proposed article:
]A team of researchers, numbering in the hundreds, combined with over 300
]awesome computers working over a seven-month period demonstrated that using
]their combined resources the capability exists to "crack" the 512-bit RSA
]key. This 512-bit key is currently used largely by E-Commerce sites that
]want to be able to do business internationally. Most of the U.S. based
]financial institutions have already made the upgrade to the 1024-bit RSA
]key.
]The actual 512-bit RSA key was not cracked. A 155-digit number that is the
]same length as the number for the 512-bit key was factored to its prime
]numbers. So the "actual" key was not factored or cracked, but a number
]similar to it was. The researchers demonstrated to the World that the key
]could be cracked, not that it was cracked. To actually crack the key,
]someone will have to duplicate the efforts of the researchers on the actual
]key. Most of the folks involved in this endeavor would not participate in an
]actual attack on a key.
]This 512 or 1024-bit RSA key is only one level of protection given to
]transactions on the Internet. Almost all public transactional Web sites use
]SSL (Secured Sockets Layer) to encrypt the data. In SSL, once the data is
]encrypted using the 512 or 1024-bit RSA key, it is encrypted again with
]ANOTHER key that's generated by the browser. This other key is different
]every time you initiate an SSL session. For those browsers using 128-bit
]Strong U.S. encryption, a Cray super computer can crack it in 2 days. The
]average group of folks would have to get together 30 or so computers,
]running in parallel, teamed up with about 5 people at least 2 weeks of 24
]hour a day operation to "crack" this second key.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Schrodinger's Cat and *really* good compression
Date: Mon, 27 Sep 1999 14:38:56 GMT
Mok-Kong Shen wrote:
> That's why I said previously that the experiment is an 'analogy'/
> 'metapohor' which Schroedinger seemed to choose to employ on grounds
> of simplicity for communicating the idea of sort of unknown/undecided
> state of quantum theory to the layman. But I think this is a
> pedagogical failure.
I suppose it is, if you keep missing the point.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: frequency of prime numbers?
Date: Mon, 27 Sep 1999 14:32:08 GMT
karl malbrain wrote:
> It's time to ANTE up guys. No, you cannot DIFFERENTIATE anything from
> ZEROES, you just get more zeroes. Have the COMPILER emit a warning message
> for( !! ) if you must, else dismiss as a SINGULARITY at run-time. Karl M
Are you a buzzword-generation program, or a person?
If the latter, pity.
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: NEMA, Swiss cipher machine
Date: 28 Sep 99 05:06:46 GMT
John Savard ([EMAIL PROTECTED]) wrote:
: As I understand it, the red rotor and two of the drive rotors move
Oh, dear, did I really say that?
I'm afraid I must put my foot down here.
I know that in electromechanical devices in general, a rotor is merely
something that rotates, and it doesn't have to also be a commutator.
And I know that the proper name for what an Enigma and a Hebern machine
are, and a Hagelin lug-and-pin machine and a Lorenz Schlusselzusatz are
not is a "wired rotor machine", not simply a rotor machine.
But because there have been erroneous and confusing references to the
latter two as "rotor machines", I wish to *strongly* urge all concerned
not to refer to anything which doesn't have wires connecting contacts
arranged in one or more circles, found in a cipher machine, as a "rotor".
Thus, only the "contact rotors" or "contact wheels" (I may have done this,
not Frode) in a NEMA should be called rotors.
A vocabulary of _meaningful_ terms is an extremely valuable thing to have
in a field to make it understandable to people.
John Savard
------------------------------
** 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
******************************
