Cryptography-Digest Digest #42, Volume #11 Thu, 3 Feb 00 05:13:02 EST
Contents:
Re: *** ECC - new strong and fast calc method (Paul Rubin)
Re: Challenge: Who can discover the encryption used here? (Tom St Denis)
Re: 26-Dimensional cipher - is it secure (or even possible)? (James Barlow)
Re: Pseudo-OTP? ("Douglas A. Gwyn")
Re: How to Annoy the NSA ("Douglas A. Gwyn")
Re: How to Annoy the NSA ("Douglas A. Gwyn")
Re: Does the NSA have ALL Possible PGP keys? ("Douglas A. Gwyn")
Re: How to Annoy the NSA (David A Molnar)
Re: Available Algorithms (David A Molnar)
Re: Help needed on peculiar use of cryptography (James Barlow)
Re: Q: current CAST status (Hideo Shimizu)
Re: *** ECC - new strong and fast calc method (David A Molnar)
Re: How to Annoy the NSA (Jerry Coffin)
Re: Available Algorithms ("G. R. Bricker")
Re: How to Annoy the NSA (Bill Unruh)
Re: How to password protect files on distribution CD (The Archmage)
How to choose public-key e on RSA? ("Miryadi")
Re: Ciphers for Parallel Computers (Anon)
Re: Reducing swap file use in Windows 98 ("Douglas A. Gwyn")
Re: Does the NSA have ALL Possible PGP keys? (H. Peter Anvin)
Re: Biggest keys needed (was Re: Does the NSA have ALL Possible PGP (H. Peter Anvin)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: *** ECC - new strong and fast calc method
Date: 3 Feb 2000 03:13:41 GMT
In article <87a6lg$1s3$[EMAIL PROTECTED]>, Greg <[EMAIL PROTECTED]> wrote:
>For example:
>
> Q[0] = 2^0 * P
> Q[1] = 2^1 * P
> ...
> Q[n-1] = 2^n-1 * p
>
>Given private key k, the public key R is calculated by:
>
>R = SUM(i=0 to n-1)[ k[i] * Q[k] ]
>
>where k[i] is either 1 or 0, depending on bit i in k.
This is a venerable and widely used technique for speeding up
modular exponentiation when the base is known in advance.
Look in Knuth vol. 2 under "Addition Chains" for far more than
you wanted to know on the topic. Brickell et al also have some
papers on fancier versions of this scheme.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Challenge: Who can discover the encryption used here?
Date: Thu, 03 Feb 2000 03:15:42 GMT
In article <pG%l4.1038$[EMAIL PROTECTED]>,
"TJ" <[EMAIL PROTECTED]> wrote:
> I have two text files, taken from a game. Originally, the file was not
> encrypted, and in an updated version, it is.
>
> I have a copy of both versions, and my question is this;
> Who can discover the encryption method used?
>
> Thanks
> TJ
>
>
Sure I know what you are talking about... um no.
BTW are you soliciting software piracy? that's a big nono.
Basically... readthefuckingfaqbeforepostingtothenewsgroupplease.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (James Barlow)
Subject: Re: 26-Dimensional cipher - is it secure (or even possible)?
Date: Thu, 3 Feb 2000 04:35:04 -0000
In article <86nuja$39r$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> I have an idea for a code whereby each set of 26 letters is enciphered
> differently (i.e. you encipher each 26-graph). To do this you would
> need a (virtual) 26-dimensional grid of numbers. Of course, there are a
> huge number of keys, because you can change not only the numbers inside
> the grid, but also all of the letters along the edges.
Sort of a Vigenere Hypercube? The overhead in populating, and storing the
cube (26*sizeof[char] ^ 26 ?) would be quite high unless you are filling
it based on some bit of clever bit of math. I don't grok how you get from
a plaintext block to a 26-dimensional index to a grid cell.
Or am I getting the wrong end of the stick? Anything beyond four
dimensions gives me a headache.
James
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Pseudo-OTP?
Date: Thu, 03 Feb 2000 04:48:00 GMT
"Trevor Jackson, III" wrote:
> A fake OTP is worthless.
It's not necessarily worthless, but it must not be confused
with an ideal OTP system.
> The term is often used by (clueless) advocates of weak
> encryption software.
That is certainly true. Sometimes they even call their
pseudo-OTP system just "OTP", but in any case they're
counting on the ideal OTP's reputation for uncrackability
rubbing off on their own product, which is usually
crackable.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: How to Annoy the NSA
Date: Thu, 03 Feb 2000 04:49:37 GMT
"Trevor Jackson, III" wrote:
> Prime P is easy to factor no matter how large.
> The factors are P and one.
We don't usually include 1 among the factors,
because then the UFT doesn't work.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: How to Annoy the NSA
Date: Thu, 03 Feb 2000 04:53:35 GMT
[EMAIL PROTECTED] wrote:
> Despite NP-Completeness, I read an
> introductory article which states "When the
> first quantum factoring devices are built the
> security of public-key cryptosystems will
> vanish. The mathematical solution to the
> distribution problem is shattered by the
> power of quantum computation". Is this
> basically true even if there are modifications
> made in RSA, etc.? Would quantum computers
> greatly reduce the need for human
> cryptoanalysts?
No, as several posters have already explained,
it is not true. Furthermore, it is not clear
that QCs can help much against many forms of
cryptosystem.
We heard similar extravagant claims when parallel
computation first caught on. Parallelism is good
for certain attacks but doesn't help much when
attacking other systems. Very similar to QC..
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: comp.security.pgp
Subject: Re: Does the NSA have ALL Possible PGP keys?
Date: Thu, 03 Feb 2000 04:59:53 GMT
Arthur Dardia wrote:
> Soft-tempest fonts? Never heard of them - enlighten me.
Essentially, they're designed to make it harder to correlate
the scans from the van Eyck radiation, thereby making it
harder to use the radiation to spy on your display screen.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: How to Annoy the NSA
Date: 3 Feb 2000 05:19:45 GMT
[EMAIL PROTECTED] wrote:
> larger primes have to be guessed at? BTW,
> Shor's algorithm can be extended to any
> algorithm computing an NP function.
Do you have a reference for this?
Thanks,
-David
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Available Algorithms
Date: 3 Feb 2000 05:27:14 GMT
Paul Schlyter <[EMAIL PROTECTED]> wrote:
>
> Is addition patented? If so, where do I have to pay royalties the next
> time I balance my checkbook? :-))))))))))))))))
I'd tell you, but the patent is in Babylonian.
(Oystein Ore's _Number Theory and Its History_ cites the Babylonians as
the first to use a positional number system; I figure other systems
are sufficiently different to escape the claims of a patent)
------------------------------
From: [EMAIL PROTECTED] (James Barlow)
Subject: Re: Help needed on peculiar use of cryptography
Date: Thu, 3 Feb 2000 05:37:31 -0000
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> Because I often have to match records across different payperiods, months and
> years, a unique identifier is required for each record, often the social
> security number.
This would seem to be a DBA problem, not a crypto problem. It would be
easier for an authorised party (internal Human Resources) to create a
database query which assembles the required data and outputs it in a form
which does not contain the SSN field, and is indexed on family name. Thus
our Economist never has access to the controlled data in any form.
This would seem easier to implement and also more secure than mucking
about with cryptography.
James
------------------------------
From: Hideo Shimizu <[EMAIL PROTECTED]>
Subject: Re: Q: current CAST status
Date: Thu, 03 Feb 2000 14:36:28 +0900
Thank you, Dr.Mike and Mr. David.
Hideo Shimizu
TAO, Japan
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: *** ECC - new strong and fast calc method
Date: 3 Feb 2000 05:30:57 GMT
Paul Rubin <[EMAIL PROTECTED]> wrote:
> This is a venerable and widely used technique for speeding up
> modular exponentiation when the base is known in advance.
> Look in Knuth vol. 2 under "Addition Chains" for far more than
> you wanted to know on the topic. Brickell et al also have some
> papers on fancier versions of this scheme.
Also Daniel Bleichenbacher's thesis has a chapter on the topic. It's the
most recent reference I know of and draws two papers presented at
various CRYPTO conferences on how to make addition chains actually
work in practice. Plus original work, of course!
Thesis is here :
http://www.bell-labs.com/user/bleichen/diss/thesis.html
I think the Handbook of Applied Cryptography has some discussion of
the topic as well.
Thanks,
-David
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: How to Annoy the NSA
Date: Wed, 2 Feb 2000 23:31:16 -0700
In article <87aqku$gkl$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
[ ... ]
> New algorithims for quantum computing are
> continuously being developed and by the time
> quantum computers are working reliably
> 2048-bit keys may be inadequate.
This, of course is true: in fact, but the time anybody has a working
quantum computer, a 2048-bit key may not even be an adequate defense
against a _conventional_ computer.
New algorithms are being developed all the time for ALL kinds of
computers, and there's no guarantee that most practical ciphers will
remain secure indefinitely. Quantum computers really have no effect
on this in either direction.
> BTW,
> Shor's algorithm can be extended to any
> algorithm computing an NP function.
Can it? I'm reasonably certain that I've never even seen a suggestion
to that effect before, or from anybody else. Do you actually have a
proof of it being true?
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: "G. R. Bricker" <[EMAIL PROTECTED]>
Subject: Re: Available Algorithms
Date: Thu, 03 Feb 2000 07:18:40 GMT
i think they used base 60 or something. however, if you get in legal
trouble, just hire a good Assyrian lawyer....
David A Molnar <[EMAIL PROTECTED]> wrote in article
<87b3ji$6e$[EMAIL PROTECTED]>...
> Paul Schlyter <[EMAIL PROTECTED]> wrote:
> I'd tell you, but the patent is in Babylonian.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: How to Annoy the NSA
Date: 3 Feb 2000 07:31:45 GMT
In <[EMAIL PROTECTED]> Jerry Coffin <[EMAIL PROTECTED]>
writes:
]than a one-time-pad are particularly vulnerable. A quantum computer
]could break RSA (for one example) more quickly than a conventional
]computer, but doubling the size of the key used brings back roughly
]the present level of security. Right now, an RSA key from about 750
Uh, no. Q comp is polynomial ( probably length of N ^2 ) so doubling the
length of the key will only make is say 4 to 8 times as hard to break.
Now a very good situation, since it takes about the same expansion to
create the key. Ie, creating and breaking the key would be about equally
difficult. However a Q comp is not exactly on the horizon yet.
]Also note that nobody's figured out ANY way to use a quantum computer
]to attack MANY (if not most) of the ciphers in use today. Just for
]example, if you could postulate that a quantum computer was available
]and ready for use right now, it would make essentially NO difference
]to the security of any of the AES finalist candidates.
Well, no. It would make a difference. The grover algorithm would reduce
exhaustive search to the equivalent of a key half the length. Ie, a 128
bit key would be about as strong under Q comp as a 64 bit key under
classical computation.
------------------------------
Date: 3 Feb 2000 07:34:38 -0000
From: The Archmage <[EMAIL PROTECTED]>
Subject: Re: How to password protect files on distribution CD
Crossposted-To: alt.security.pgp,comp.security.unix
On 2 Feb 2000 18:34:43 GMT, Alan J Rosenthal <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] (Vernon Schryver) writes:
> >Alan J Rosenthal <[EMAIL PROTECTED]> wrote:
> >If you want that something close to that mode, then use the MAC address
> >of an Ethernet board, and treat the Ethernet board like an old fashioned
> >dongle.
>
> I did mention MAC addresses later in my article, but if you're contemplating
> the replacement of the entire computer, well, the ethernet hardware is part of
> the computer. Not necessarily on a separate card at all, and besides you
> might want to replace your ethernet card while replacing the rest of your
> computer, or the ethernet card might break and you might replace it, ...
Let alone the fact that MAC addresses are changeable in software and is
equivalent to a simple serial number scheme which takes all of 10 minutes to
hack. Pretend you are using an USB-based dongle that actually implements good
challenge/response and only decrypt info as needed. This would actually be
not a bad solution as those kinds of solutions go.
> Also, as I understand it, the ethernet standard specifies that the
> MAC address is part of the computer, not specifically the ethernet hardware
> and ideally not; and in fact most non-personal-computers have their MAC
> address somewhere else on the motherboard; it doesn't change when you
> exchange ethernet cards; it DOES change when you change motherboards and
> use the old ethernet card.
There are many good reasons to change an ethernet/network card. Many times
have I upgraded segments at a time with new cards. I wouldn't like for X
pieces of software to break. A dongle since it has only one task and it is
clear to the user won't have this problem. Note that many software based
licensing schemes use IP and MAC addresses as input to their *node-UID*. They
can break during any hardware upgrade and some during renumbering a network.
Very annoying and damaging to timetables. It is also not obvious to the
sysadmins since licensing schemes are security through obscurity and don't
document their inputs as it weakens the security.
>
> >I think most software vendors that are charging real money (i.e. not
> >shareware pricing) prefer to know when you buy a new computer and many
> >even prefer to force you to buy a new license. (I'm reporting not
> >commending the attitudes of some business and sales people
BS. I know people who work in the licensing industry. There is a percentage
who feel the way you do but *most* is a large strech. I would say the
assholes feel that way. Most don't care for the support overhead, let alone
the number of _free_ licenses they will have to give away to fix stupid
self-imposed problems. For real money I see two common methods.
X simultaneous users/X licensed users (variations on a theme)
and
Site License (site may be subnet)
> >>This is not to say that I approve of dongles, but I don't think the
> >>license-manager type schemes are better. (And I really wish I had heard
> >>about those "I hate FlexLM" T-shirts in time to buy one.)
I agree. Dongles are a better solution and one that can be lived with. Much
less intrusive. Especially if it is a USB or other bussed device.
[SNIP globally unique stuff]
> >On the other hand, in the real world, things like MAC addresses that have
> >actual mechanisms aren't always unique. ...
>
> I'm not saying you ignore these factors. I'm saying you start with solid
> theory, then you modify as needed for practical reasons, and then you end up
> with a scheme which works in theory AND in practice. Otherwise you typically
> end up with a system which works in neither.
And MAC addresses is one of those. To be honest dongles are not a terrible
solution though not without flaws and certainly not unbreakable.
--
The Archmage : We are watching...
[EMAIL PROTECTED] : ... and being watched.
------------------------------
From: "Miryadi" <[EMAIL PROTECTED]>
Subject: How to choose public-key e on RSA?
Date: Thu, 3 Feb 2000 15:04:26 +0700
Hello, Everybody
I have a problem on determining the number of step
to find public-key, e, on RSA algorithm.
My procedure in Delphi is like this:
Procedure SearchForE;
var found: boolean;
begin
e:= random(100);
if e mod 2=0 then e:=e+1;
found:=false;
repeat
if GCD(e, (p-1)*(q-1))=1) then found:=true
else e:=e+2;
until found:=true;
end;
Is it possible to determine how many number I should examine,
before finding e.
TIA
Best Regards
-- Yadi --
------------------------------
From: Anon <[EMAIL PROTECTED]>
Subject: Re: Ciphers for Parallel Computers
Date: Thu, 03 Feb 2000 09:34:58 +0100
John Savard schrieb:
> [you can do cryptology on a parallel computer with xoring many
> functions which work in a feistel network].
Far too complicated. Just use interlaced CBC mode so you can use
any block cipher in parallel:
________________________________________________
ENCRYT(x) : encryption routine
IV : initialization vector (some random data)
CC : cpu/processor count
A : array [0..CC-1] of block
INPUT() : next input block
Algorithm:
A[0] = IV
for i in range(1, CC-1):
A[i] = ENCRYPT(INPUT() XOR A[i-1])
while not empty:
emit A[0..CC-1]
forall i in range(0, CC-1) parallel:
A[i] = ENCRYPT(INPUT() XOR A[i])
________________________________________________
It is easy to see that the basic encryption step can be done
in parallel for any number of processors. The only problem
you'll get is to distribute the input data, and to collect
the output data. But you'll get the same problem with your
approach, and even far worse than with the algorithm above,
because you have to send ALL data to ALL processors.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Reducing swap file use in Windows 98
Date: Thu, 03 Feb 2000 08:58:39 GMT
Tim Tyler wrote:
> I presume operating systems /should/ - upon request - allow applications
> access to memory that is guaranteed not to be visible to other processes,
> or written out to magnetic media without permission.
An OS interface that supports application requests for such things
is way too complex. If the OS is going to support security, it
should do it by default.
------------------------------
From: [EMAIL PROTECTED] (H. Peter Anvin)
Crossposted-To: comp.security.pgp,misc.survivalism
Subject: Re: Does the NSA have ALL Possible PGP keys?
Date: 3 Feb 2000 01:41:53 -0800
Reply-To: [EMAIL PROTECTED] (H. Peter Anvin)
Followup to: <[EMAIL PROTECTED]>
By author: cfm <[EMAIL PROTECTED]>
In newsgroup: sci.crypt
>
> According to Maple, the number of primes in a 512 bit RSA calculation
> (256 bit primes) is:
>
> Li((2^257)-1) - Li(2^256) = .6511328131 10^75
>
> Additionally approx number of 512 bit primes:
>
> Li((2^513)-1) - Li(2^512) = .3773896853 10^152
>
> and number approx number of 2048 bit primes:
> Li((2^2049)-1) - Li(2^2048) = .2275922921 10^614
>
> Li(x) is the integral logarithm, which approximates the prime function
> (pi(x)), and counts the number of prime numbers up to x. the above
> calculations compute the number of prime numbers between the largest of
> a particular bit size y ((2^y)-1) and the smallest (2^y).
>
> Yes these are very large #'s and no I don't think that anyone would
> calculate them. The number of CAST IDEA or 3DES (3key) keys are on the
> order of 10^38 or 10^51, again big but not impossible. But how to search
> it ....
>
Note that PGP *does* use IDEA or 3DES -- depending on version -- to
actually encrypt the message (the RSA or DSS/ElGamal keys are only
used to encrypt the session key.) Consequently, if IDEA or 3DES is
broken, so is PGP. This is *still* not something you do by exhaustive
search. However, if there is a Trojan RNG generating session keys in
some version of PGP (very unlikely, IMNSHO) it could be used to narrow
the keyspace.
-hpa
--
<[EMAIL PROTECTED]> at work, <[EMAIL PROTECTED]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
------------------------------
From: [EMAIL PROTECTED] (H. Peter Anvin)
Subject: Re: Biggest keys needed (was Re: Does the NSA have ALL Possible PGP
Date: 3 Feb 2000 01:48:02 -0800
Reply-To: [EMAIL PROTECTED] (H. Peter Anvin)
Followup to: <[EMAIL PROTECTED]>
By author: [EMAIL PROTECTED]
In newsgroup: sci.crypt
>
> Trevor Jackson, III wrote:
> > This issue came up a few months ago. If every possible position in the
> > observable universe is a computer that tests a key in the Fermi time and they
> > all run until the breakdown of protons (1e31 years by a stale theory), then you
> > need a key of ~870 bits to prevent it being found.
>
> Cool!
>
> > QC gives you around sqrt() advantage, so doubling the key yields about the same
> > strength.
>
> Ah! I didn't know that bit. Neat. Thank!
>
> So, like, a 2048-bit key is way overkill. Good. :-)
>
Most public key cryptosystems don't have a dense keyspace. You have
to "densify" the keyspace before making comparisons. In the case of
cryptosystems using primes, there is a formula for the prime density
that you can apply.
I believe Trevor was referring to a *dense* 870-bit keyspace.
-hpa
--
<[EMAIL PROTECTED]> at work, <[EMAIL PROTECTED]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
------------------------------
** 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
******************************
