Cryptography-Digest Digest #777, Volume #13 Fri, 2 Mar 01 07:13:00 EST
Contents:
Re: RSA Key Generation (Paul Schlyter)
Re: RSA Key Generation (Paul Schlyter)
Re: encryption and information theory ("Mxsmanic")
Re: => FBI easily cracks encryption ...? ("Mxsmanic")
Re: => FBI easily cracks encryption ...? ("Mxsmanic")
won't you tell me something about my encryption scheme ? (yomgui)
Re: philosophical question? (Joe H. Acker)
Re: Urgent DES Cipher source code !!!!! (Panu =?iso-8859-1?Q?H=E4m=E4l=E4inen?=)
Re: => FBI easily cracks encryption ...? ("Sam Simpson")
Re: How good is the KeeLoq algorithm? (S�ren A.M�ller)
Re: OverWrite freeware completely removes unwanted files fromharddrive
(network_noadle)
Re: => FBI easily cracks encryption ...? (Mok-Kong Shen)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: RSA Key Generation
Date: 2 Mar 2001 10:35:39 +0100
In article <HlGn6.188$[EMAIL PROTECTED]>,
Roger Schlafly <[EMAIL PROTECTED]> wrote:
> "Mark Reed" <[EMAIL PROTECTED]> wrote in message
> news:2cGn6.56062$[EMAIL PROTECTED]...
>> My question is whether this is common practice, or if generally the top
>> two bits of each prime (guaranteeing n > 0x90......)
>
> Both are common. Setting the top 2 bits is an easy way to guarantee
> that the product has the right number of bits. But also generating
> a 1024-bit modulus and really getting one that is 1023 bits is not
> a problem either.
It will immediately become a severe problem if you use that key to
encrypt a cleartext which is 1024 bits, since then you won't get your
cleartext back intact after decryption. This will happen as soon
as your cleartext is larger than your modulus.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: RSA Key Generation
Date: 2 Mar 2001 10:35:12 +0100
In article <2cGn6.56062$[EMAIL PROTECTED]>,
Mark Reed <[EMAIL PROTECTED]> wrote:
> In RSA key generation, 2 primes are found by getting random data and setting
> the most and least significant bits are set to ensure the prime length is
> half the required modulus length and that it is odd.
> Then this is checked, then the next candidate (say by adding two) until
> it is 'probably prime' enough for use.
>
> If only the top bit is set, the key length may be one less than required -
> as an example for a 512 bit RSA key with
> p = 0x80......
> q = 0x80......
>
> then
>
> n = 0x40......
>
> My question is whether this is common practice, or if generally the top two
> bits of each prime
> (guaranteeing n > 0x90......)
Guaranteeing n > 0xC0 !!!!!!
> I suppose another possibility is that primes are generated until n is the
> required bitlength.
>
> Unless this method is used, isn't security compromised ? ie. n can be
> less than the number of bits required or the top two bits of each prime
> are known to be one.
The problem to be solved by this is that the modulus n must always be
larger than the cleartext you want to encrypt. If the cleartext is larger
than the modulus, then after decryption you won't get your cleartext
back, but instead youll get cleartext mod n.
One way to handle this is to, if you can detect whether the cleartext
is correct or not, add back n to cleartext until you get the correct
cleartext.
Another way, and the most common way, is to make sure the modulus n
always is larger than the cleartext.
If your cleartest is ASCII data, or if it for some other reason the
cleartedt always will have its highest bit clear, then ensuring that
the modulus n always has its highest bit set is a way to ensure that
the modulus always is larger than the cleartext.
If your cleartext is binary data the situation gets more complex.
One way is to format your binary data such that the highest bit always
is zero. If you don't want to do this, all which remains is to generate
RSA keys such that the X topmost bits of the modulus are one;
then the probability of the binary cleartext being larger than the
modulus is 2^(-X).
By always setting the X topmost bits of your modulus to one, you
will, form a security point of view, lose X bits of your RSA key
size. Since X usually is a small number (1 or 2, sometimes perhaps
somewhat larger) this is usually not a problem, but if you think this
is a problem, it can easily be circumvented by increasing the size of
the RSA key somewhat.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: "Mxsmanic" <[EMAIL PROTECTED]>
Subject: Re: encryption and information theory
Date: Fri, 02 Mar 2001 10:27:45 GMT
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Oh? Suppose I have a message, which was 128
> bits from a TRNG. Now I encrypt with Rijndael,
> using a 128 bit blocksize, and 128 bit key, where
> the key was also generated by a TRNG.
> Now I send that ciphertext. Are you saying that
> the 128 bit ciphertext has 256 bits of entropy?
No, the entropy (information content) does not change with encryption.
------------------------------
From: "Mxsmanic" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,talk.politics.crypto
Subject: Re: => FBI easily cracks encryption ...?
Date: Fri, 02 Mar 2001 10:37:18 GMT
"Jeff Moser" <[EMAIL PROTECTED]> wrote in message
news:97n22f$g7d$[EMAIL PROTECTED]...
> The point is, I don't think this guy was stupid
> enough to use poor encryption.
He wouldn't have to be stupid; he could just be na�ve.
------------------------------
From: "Mxsmanic" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,talk.politics.crypto
Subject: Re: => FBI easily cracks encryption ...?
Date: Fri, 02 Mar 2001 10:38:14 GMT
"groj" <[EMAIL PROTECTED]> wrote in message
news:97n8l8$mk5$[EMAIL PROTECTED]...
> One would presume that government computers at
> that level would all be recorded as a matter of
> course??
I might presume that for an agency like the NSA, which has considerable
experience in establishing and maintaining security. I would not
presume that for the FBI, which has traditionally been more concerned
with things like guns than with Gaulois fields.
I suspect that FBI PCs are essentially identical to any other PCs.
------------------------------
From: yomgui <[EMAIL PROTECTED]>
Subject: won't you tell me something about my encryption scheme ?
Date: Fri, 02 Mar 2001 10:44:34 +0000
hello,
I've developped my own, quite simple, encryption method.
the source code is here http://bigfoot.com/~kryptyomic
under the GNU Lesser General Public License.
I describe here in few lines how it works.
could you tell me what you think of it.
I avoid the biggest mistakes, but you will probably
find out some weakness that I missed.
thanks, guillaume
Kryptyomic encryption scheme:
each letter of a password up to (256*256 bytes) is used as an unsigned
byte integer value to seed a pseudo-random serie, a simple combo from
the public domain: the period of the combo exceeds 2^60
this combo can be replaced by any other pseudo random number generator.
each random series is seeded with the password plus a pseudo random
number from the previous serie.
these series are used in random order to produce one new pseudo random
number, and to determine the next series to use.
then we use the next series to produce one number, and so on.
the pseudo random series are used to generate an encryption grid
this grid allows the replacement of a two-byte value by its
corresponding unique two-byte value in the grid.
a smaller grid of 256 bytes is used when single-byte encoding is
necessary.
the stream is considered as a succession of two-byte values.
the value is obtained from the stream: val0
we generate one two-byte pseudo random number: aTwoByteRandNumber
we xor them together: val1 = val0 XOR aTwoByteRandNumber
we take the corresponding value in the grid: val2 = grid[val1]
we xor with the same random number: val3 = val2 XOR aTwoByteRandNumber
we put the value in the output stream. val3
note: if we don't do the grid corresponding step, no encryption is
performed. (ie. if val2 equals val1 then val3 equals val0).
to perform decryption we follow the same method but before running the
stream, we just reverse the grids once (such as val1 =
reversegrid[val2])
------------------------------
From: [EMAIL PROTECTED] (Joe H. Acker)
Crossposted-To: sci.crypt.random-numbers,de.sci.informatik.misc,sci.math
Subject: Re: philosophical question?
Date: Fri, 2 Mar 2001 12:07:28 +0100
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> "Joe H. Acker" wrote:
> > but when I listen to white noise in my radio, it might not.
> > Randomness itself does not convey any information, ...
>
> It certainly does, it's just not information that has value to you.
> It could well have value in other contexts.
Yes, I think we agree. That's what I was pointing out: It can only
convey information relative to a sign-system, and information-theory can
also only be applied relative to a sign-system in consideration (or call
it a "code"). Of course, you can use a TRNG to distribute very short
impulses randomly over many different frequencies. If the impulses
cannot be identified as being articial, and the other party has a copy
of the pre-recorded TRNG output, you have a nice steganographic OTP
communication channel, although it's true random white noise in my
radio. I'd bet that's the way spies talk with their mom. :)
Maybe I am confused by the notion of randomness people seem to use on
sci.crypt. If you take two events A and B as a sign for something, and
the probability that A will occur is exactly one half, and the
probability that A or B will occur is exactly one (no source of error),
then the actual occurance of A or B will be truly random. This can be
extended to an exact definition of randomness for any sign-system and
channel under consideration, can't it? But here, people seem to use
randomness in the sense of unpredictability, but that's something
different. Why? Because if a TRNG happens to output 1 a few hundred
times in sequence, which is quite inprobable but can happen, then there
should be a high-probability that next time it will output a 0. That's
of course the reason why there's a limit in roulette, because otherwise
you could use the well-known strategy to bet on odd, double the amount
of money if you loose and bet it on even and so on, or start from the
beginning if you win.
I've understood the original question in the way, wether there is a
sign-system not invented by humans, that could be applied to true random
sequences and convey some information (in the ordinary sense of
"information"). I don't think so, but anyway, that's a religious
question. And you cannot even apply information theory to a true random
sequence, if you have no clue about the sign-system used. The term
"information-theory" and its notion of "information" wasn't a
particularly good choice of terminology. (I'm not sure but I think I've
once heard that even Shannon was unhappy about it later.) It would have
better be named probabilistic coding theory.
Greetings,
Erich
P.S. Sorry about the silly psyeudonym and wrong mail address. I don't
want anyone to make stupid assumptions about me ten years later. There
should be an option to delete messages in Usenet archives after a few
months.
------------------------------
From: Panu =?iso-8859-1?Q?H=E4m=E4l=E4inen?= <[EMAIL PROTECTED]>
Subject: Re: Urgent DES Cipher source code !!!!!
Date: Fri, 02 Mar 2001 13:22:26 +0200
http://people.qualcomm.com/karn/code/des/index.html
-- Panu
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,talk.politics.crypto
Subject: Re: => FBI easily cracks encryption ...?
Date: Fri, 2 Mar 2001 11:30:04 -0000
Mxsmanic <[EMAIL PROTECTED]> wrote in message
news:qKKn6.2060$[EMAIL PROTECTED]...
> "groj" <[EMAIL PROTECTED]> wrote in message
> news:97n8l8$mk5$[EMAIL PROTECTED]...
>
> > One would presume that government computers at
> > that level would all be recorded as a matter of
> > course??
>
> I might presume that for an agency like the NSA, which has considerable
> experience in establishing and maintaining security. I would not
> presume that for the FBI, which has traditionally been more concerned
> with things like guns than with Gaulois fields.
Very true. BTW it's 'Galois'.
> I suspect that FBI PCs are essentially identical to any other PCs.
For normal, run of the mill machines yes, I don't doubt it. For machines
storing classified information, the NSA secure facility rules take over -
this hardware / software is likely to be quite different from standard pc's.
Regards,
Sam
------------------------------
From: S�ren A.M�ller <[EMAIL PROTECTED]>
Subject: Re: How good is the KeeLoq algorithm?
Date: Fri, 02 Mar 2001 11:39:10 GMT
On Fri, 02 Mar 2001 10:54:02 +0100, Frank Gerlach
<[EMAIL PROTECTED]> wrote:
<snip>
>> Does there exist any analysis og the KeeLoq crypto algorithm?
(whoops, a typo - I meant 'of' not 'og'.)
>Never heard of it.
There is an introduction to KeeLoq here:
http://www.microchip.com/10/appnote/category/keeloq/91002/index.htm
> Secret algorithms are always a bad sign in cryptography.
Well it is not a total secret.
As I mentioned you can buy the decryption part without any problems.
What you get is the decryption source code and a licence agreement (that you
don't need to sign).
<snip>
> Why can't they use a standard algorithm such as DES or RC4 ??
Probably because the algorithm output should be short (32 bits) and it is
implemented in a low cost microcontroller with limited capabilities.
It is inplemented with the use of single bit rotations, xor and a very small look-up
table only.
> Sounds like the russian car mafia should have a look at that :-))
They probably allready have :-)
Isn't it easier to move the car to someplace else and remove the car alarm etc.?
--
S�ren A.M�ller
------------------------------
Crossposted-To: alt.hacker
From: network_noadle <[EMAIL PROTECTED]>
Subject: Re: OverWrite freeware completely removes unwanted files fromharddrive
Date: Fri, 2 Mar 2001 11:44:35 +0000
On Thu, 1 Mar 2001, Anthony Stephen Szopa wrote:
<snip>
>
> If what the noadle says is true then nothing you instruct the computer
> to do that may ever be considered redundant by his definition will ever
> get executed because after all, your one GHz cpu is cranking out those
> computations and source code instructions at such a fast rate all your
> peripheral devices fall behind as soon as the second instruction code
> is read.
>
> The noadle just trashed any and all hope any of you have or ever had
> that when you write a computer program that you can ever count on those
> instructions being carried out.
>
> FUD!
>
> The noadle and any who believe his rubbish are absolutely LAUGHABLE!
>
One word. Bullshit!
You obviously have no idea how write behind caching works, either at the
system memory level, or the peripheral device level. In order to increase
the throughput of a peripheral block device, such as a disk, the OS
doesn't tie up valuable computation resources with handling device IO
until is becomes absolutely necessary. Check the block device source code
of the Linux kernel. I'd tell you to look at the Windows OS kernel code as
well, except that MS haven't made it available yet.
Background
==========
The way the system works is this: A program requests that a block is
written to the disk drive. The OS processes this request and buffers the
write command. In this way the program can continue on its merry way much
faster than if it was forced to wait for a slow device to complete the
request.
If *ANY* program tries to access the same block, the OS first looks in its
internal buffers. Pages in memory are read/written in preference to those
on the device: it's faster. Several orders of magnitude faster. At some
suitable/necessary point, usually when nothing else is going or the write
cache is full, the OS kicks out all the queued write requests.
The system takes a much smaller performance hit working this way than if
it is constantly stopping to read/write a device.
Conclusion
==========
If a program writes to a block on a device through the OS then that
request is put in the devices write cache. (Often referred to IIRC as a
dirty page; the hardware data is now out of date.)
If your program writes to the same block before the OS has flushed the
write cache then the block currently held in the cache will be replaced
with the new block.
So far the /original/ data that is being overwritten is still on the
hardware. The overwriting pattern is held only in the write cache.
Assuming the software runs fast enough it can write all the overwrite
patterns into the write cache, which optimises them to discard the
preceeding write.
The unavoidable result of this is that only the last pattern will reach
the disk, unless you can force the system to flush the write cache after
you have written each overwrite pattern.
As I previously stated: since the operating system knows that the blocks
in its write cache are part of a specific file, sending a `delete file'
request /may/ result in the dirty blocks being dropped from the write
cache altogether. If this happens then the data your program was supposed
to securely delete is still available, and in pristine condition.
End Piece
=========
I suggest you refer to a good book on operating system design
fundamentals. A good place to start is `Design of the Unix Operating
System' by Bach. It was published in 1986, so I recommend you start at
your nearest library.
network_noadle
PS: If you want accuse me of FUD, I suggest you learn the subject at hand.
Fast.
--
Bill: We are Microsoft.
Resistance is futile.
You will be migrated.
Me: Bill, meet Tux. Tux, eat Bill.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,talk.politics.crypto
Subject: Re: => FBI easily cracks encryption ...?
Date: Fri, 02 Mar 2001 13:03:08 +0100
Frank Gerlach wrote:
>
[snip]
> Physically securing a crypto device is always a precondition of good
> security.
> But don't expect the Palm to be any better than your PC. Someone could
> use a flaw in the PalmOS and quietly suck some data from your Palm the
> next time you put it into the cradle.
> And if the Palm is used like a PC (with lots of third-party programs)
> then there are a lot more opportunities...
> And if you are absolutely paranoid, even hardware flaws could provide an
> opportunity for attack.
Maybe one has also to care electromagnetic emanations.
M. K. Shen
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
