December 2003 - cypherpunks-legacy

Fiat's Batch RSA
by Anonymous 17 Dec '03

17 Dec '03

Batch RSA invented by Amos Fiat Described in Crypto 89 and J Cryptology 1997. RSA works as follows. The key owner chooses two secret primes p and q, and forms their product n = p*q. He then chooses a public exponent e relatively prime to p-1 and q-1. His public key is (n, e). To encrypt a message m into cyphertext c, m is raised to the power e, mod n: c = m^e mod n. To decrypt the message, the key holder calculates d as the multiplicative inverse of e mod (p-1)(q-1): d = 1/e mod (p-1)(q-1). He recovers m from m = c^d mod n. For simplicity, below we will write this as m = c^(1/e) mod n, where it is understood that the 1/e is done mod (p-1)(q-1). An RSA signature s on a message m is calculated as for a decryption: s = m^(1/e) mod n. The signature is verified by m ?=? s^e mod n. The time consuming part of an RSA decryption or signature is this exponentiation step. e can be chosen to be small, so encryption and verification is fast, but 1/e will generally be about the same size as n, so many multiplications must be done to raise a number to that power. Amos Fiat describes a method whereby multiple messages can be decrypted or signed using only one full-sized exponentiation. The "catch" is that the messages must all use different exponents with the same n. Here is a concrete example. You want to decrypt or sign two messages, M1 and M2, raising M1 to the 1/3 power and M2 to the 1/5 power. Perform the following steps: M12 = M1^5 * M2^3 I12 = M12 ^ (1/15) This is the only full-sized exponentiation needed. This gives: I12 = M1^(1/3) * M2^(1/5). This is the product of the two values that we want. Fiat uses a trick to disentangle the two values. He raises I12 to the 6th power. The number 6 is chosen so that it is a multiple of one of the two exponents, 3, and is 1 more than a multiple of the other exponent, 5: I12^6 = M1^2 * M2 * M2^(1/5) Therefore: M2^(1/5) = I12^6 / (M1^2 * M2) which is one of the values we need. Since I12 is the product of the two values we want, we can recover the other value just by dividing this into I12: M1^(1/3) = I12 / M2^(1/5) Here is another example. Suppose we want M3^(1/7) and M4^(1/11). (Note that we are using prime numbers for the exponents; the reason will be explained below.) We calculate: M34 = M3^11 * M4^7 I34 = M34 ^ (1/77) This gives us: I34 = M3^(1/7) * M4^(1/11) Again this is the product of the two values we want. As before we will raise this to a power which is 1 more than a multiple of one of the two exponents (7 and 11) and is a multiple of the other one. The smallest such power is 22. I34^22 = M3^3 * M3^(1/7) * M4^2 So we can divide to get M3^(1/7): M3^(1/7) = I34^22 / (M3^3 * M4^2) And we can divide to get the other value needed: M4^(1/11) = I34 / M3^(1/7) This illustrates how to derive two RSA roots using only one full sized exponentiation. A few small exponentiations are also needed, as well as two divisions, but these are much faster than doing the full exponentiation (raising to the 1/15 or 1/77 powers above). Fiat's idea can then be applied recursively. Note that in the examples above we had to take two full-sized exponentiation, M12 to the 1/15 power and M34 to the 1/77 power. We can combine both of these exponentiations into one just as was done above: M14 = M12^77 * M34^15 I14 = M14 ^ (1/1155) Now: I14 = M12^(1/15) * M34^(1/77) the product of the two values we want. We need an exponent which is 1 more than a multiple of 15 while being a multiple of 77, giving 615, or vice versa, giving 540. Choosing the latter since it is smaller we have: I14^540 = M12^36 * M34^7 * M34^(1/77) so: M34^(1/77) = I14^540 / (M12^36 * M34^7) and dividing gives the other factor: M12^(1/15) = I14 / M34^(1/77) These values can then be fed into the expressions above to recover M1^(1/3) and the other three values, all with only one full-sized exponentiation for the four messages. In general, finding the exponent for Ixx can be handled by the Chinese Remainder Theorem. However it requires that the two values be relatively prime. That is why the exponents used in Batch RSA must all be relatively prime, so that there is a solution to the value of the exponent for Ixx. As the number of values in the batch increases, the "small" exponents needed to recover the values increase as well. We saw above that the exponents went from 6 and 22 for the size-two batches to 540 for the size-four batch. This means that you reach a point of diminishing returns where increasing the batch size no longer provides much benefit. Fiat suggests a batch size of n/(log^2 n) messages, where n is the length of the full-sized exponentiation (e.g. 1000 for a 1000 bit modulus). This would correspond to about a 10 message batch for a 1024 bit key. Fiat describes a few situations where it may be appropriate to use different exponents for multiple RSA operations. In the case of a server issuing multiple RSA signatures it could define its public key to be (n, e1, e2, e3,...) and specify that the signature was valid for any exponent in the list. Then it could batch up signatures and use a different exponent for each one. Another case is "pure RSA" encryption, where the message itself is broken into blocks and each one is RSA encrypted. In that case the blocks could use successive exponents from the list, and the receiver could decrypt a batch of blocks using one large exponentiation. There is another case of interest to us, related to the task of searching through messages from a message pool, possibly steganographically hidden. That will be described in another message.

1 0

More on Association for Interactive Media conference
by Declan McCullagh 17 Dec '03

17 Dec '03

[This is the conference Tim was criticizing yesterday. --Declan] ---------- Forwarded message ---------- Date: Wed, 7 Jan 1998 10:49:01 -0800 (PST) From: Declan McCullagh <declan(a)well.com> To: politech(a)vorlon.mit.edu Subject: FC: More on Association for Interactive Media conference Netly articles on AIM: http://cgi.pathfinder.com/netly/editorial/0,1012,1155,00.html http://cgi.pathfinder.com/netly/editorial/0,1012,1464,00.html -Declan ---------- Forwarded message ---------- Date: Wed, 07 Jan 1998 10:24:20 -0800 From: John Gilmore <gnu(a)toad.com> To: declan(a)well.com, gnu(a)toad.com Subject: Re: FC: Association for Interactive Media conference (DC, 2/98) [for forwarding if you like] Note that AIM, the sponsors of the "WashingtonWeb" conference, are the folks who appear to be paid stooges for Network Solutions in trying to keep their ten million dollar per month monopoly on domain names. AIM's coverage of that issue has been completely false and completely biased ("The Internet is likely to break apart on October 15, 1997"; "you may lose all rights to use your trademark in your Internet address forever". See www.interactivehq.org/oic/) They've been deliberately making false statements to stir up sentiment against the evolution of domain names away from the Network Solutions monopoly. I wouldn't promote or attend their conference. There's something going on there that I don't understand -- but I do recognize slime when I see it. John Gilmore -------------------------------------------------------------------------- POLITECH -- the moderated mailing list of politics and technology To subscribe: send a message to majordomo(a)vorlon.mit.edu with this text: subscribe politech More information is at http://www.well.com/~declan/politech/ --------------------------------------------------------------------------

4 10

FCC squeezes the ham TV band
by David Miller 17 Dec '03

17 Dec '03

Wednesday January 7 10:22 AM EST FCC Reallocates Lightly Used Television Spectrum WASHINGTON (Reuters) - The Federal Communications Commission said Tuesday it had reallocated lightly used television frequencies for use by public safety services. Portions of the spectrum between 746 and 806 megahertz that had carried channels 60 to 69 will be given over to police and fire departments and other emergency services. The remainder of the spectrum will be auctioned off for commercial use. The reallocation was required by the Balanced Budget Act of 1997. The FCC had previously announced it would reallocate the lightly used spectrum in an April, 1997 plan for the transition to digital television. FCC chairman William Kennard said on Tuesday the commission would allow some users of the high channels to continue operations, however. "While recovery of unused spectrum is an integral part of the FCC plan for transition from analog to digital television, I am sensitive to the effects of spectrum recovery on Low Power TV and TV translators," Kennard said in a statement. Such broadcasters may continue operations through the transition to digital television "as long as they do not cause harmful interference to primary services," he said. ----------------------------------------------------------------------- Copyright © 1997 Reuters Limited. All rights reserved. Republication or redistribution of Reuters content is expressly prohibited without the prior written consent of Reuters. Reuters shall not be liable for any errors or delays in the content, or for any actions taken in reliance thereon

1 0

Re: Sentencing for Electronic Copyright Infringement
by Information Security 17 Dec '03

17 Dec '03

> Subject: Re: Sentencing for Electronic Copyright Infringement > From: dlv(a)bwalk.dm.com (Dr.Dimitri Vulis KOTM) > Date: Wed, 07 Jan 98 08:09:32 EST > > Tim May <tcmay(a)got.net> writes: > > When the ninja narc raiders cart our computers off for analysis, I'm sure > > they can find enough violations to send us away for as many years as they > > wish. > > And if Timmy knew a bit more about cryptography than he could learn by browsing > through Bruce Schneier's book, the ninja narc raiders wouldm't be able to find > shit on any of his media. :-) Hey, Vulis, how does it feel to know all your phone lines are being monitored by the FBI? For (among other things): soliciting funds for terrorist groups incl Hamas to kill a couple, and threatening government employees... ---guy Lon T. Horiuchi was indicted for murder today. The DOJ refused to prosecute him: the state will.

1 0

Re: The Digital Society Group
by jalonz＠openworld.com 17 Dec '03

17 Dec '03

>>Without getting into too much detail, The Digital Society Group is >>constructing a pure-technology infrastructure to provide for the operation, >>governance and existence of a complete digital society within a free >>enterprise zone. >The web site doesn't explain what methods you are using to establish these >zones. Do you have a mailing list set up for discussion? The plan >sounds interesting and ideologically supportable, but I'm skeptical. Blanc, I'm trying to get more docs online ASAP to explain things. The physical free zones are very popular in the interational business world, but I as a computer type had never heard of them other than Hong Kong, etc. When a country wants to set up a free zone, they come to Openworld and its partner companies who do everything from clearing land, construction, setting up businesses, schools, hospitals, etc. One of the soon to be required components of a free zone installation is a digital infrastructure to link all of the things together. We're talking smart cards for physical structure security and personal ID, email, web hosting, net access, all kinds of stuff. Since we are building a "country" from scratch, rather than have to automate paper workflows and do document management, the governance processes are designed to be digital from the start. Thus, to provide incorporation services to its citizens, a free zone allows them to sign up via web browser, and the daily maintenance, processing and management of the corporate records is also done almost exclusively via web browser and email. Its fast, cheap, and requires far less labor than a paper-based system. Another feature is that rather than maintaining the records for the customer, the customer can log in via web browser and update their own corporate record. (similar to Internic) This reduces labor even further and reduces the cost of incorporation to around $100 per year making instant offshore incorporation accessible to the general global public for the first time. That kind of solution applied across an entire governance and communications infrastructure make for some radical things to become possible. Another concept being implemented is that each new free zone (being fully wired) can easily replicate records and data with other free zones (they will actually be required to for certain things) and thus a citizen in one free zone can access banking, etc. services (even physical access) in another. So, we see the emergence of a phsically distributed, digitally cohesive network of "corporate states". This lends to applications like data protection and hiding via distributed storage or data sharing via common dataspaces and replication. The technical methods to perform all of this work are a bit touchy. At the risk of starting endless flame wars, I was looking at Lotus Bloats for its replication and hierarchical security structure as well as easy forms to web publishing and workflow management. That got shot down at the thought of actually administrating the mess and also the costs are fairly significant. The final nail in the coffin was the encryption key escrow fiasco with the Swiss. I was also looking at NT due to the nice database-to-web interface and the fact that IIS 4 isn't too bad. But again software license costs are large and who knows if Microsoft is doing, or will do, a key escrow deal for future products? Who knows what they are doing now with NT on the OS level? You can't run around making structures which allow people around the world to move money and communicate anonymously, incorporate and have software agents be owners of property and bank accounts without someone getting very pissed off. Thus, a good solution seems to be Linux in that its cheap, Unix is good for multi-process routing, and the toolkits and components created by the Digital Society can be easily moved into the public domin in some form or another. Also, the export mess can be gotten around in one way or another. Any comments? Any better alternatives than Linux? The coding being done now is either cross-platform or prototype which will be scrapped as soon as the kinks are worked out and the real fun can begin. The Digital Society is purposefully working cheap and small to enable the tools and communities to be deployed at as close as possible to no cost for the end-user - that is the priority. Most things are being coded from scratch to ensure security and keep the costs low. Labor is cheap - when its your own. :) Jalon --------------------------------------------------------------- Jalon Q. Zimmerman, Director The Digital Society Group A division of Openworld, Inc. http://www.openworld.com/ jalonz(a)openworld.com --------------------------------------------------------------- The government is not your mommy. ---------------------------------------------------------------

1 0

Polycratic government?...
by Jim Choate 17 Dec '03

17 Dec '03

Hi, Is anyone aware of research or writings regarding polycratic political systems? Thanks. ____________________________________________________________________ | | | Those who make peaceful revolution impossible will make | | violent revolution inevitable. | | | | John F. Kennedy | | | | | | _____ The Armadillo Group | | ,::////;::-. Austin, Tx. USA | | /:'///// ``::>/|/ http://www.ssz.com/ | | .', |||| `/( e\ | | -====~~mm-'`-```-mm --'- Jim Choate | | ravage(a)ssz.com | | 512-451-7087 | |____________________________________________________________________|

1 0

No Subject
by Mix 17 Dec '03

17 Dec '03

Tim C. May's reheated, refurbished, and regurgitated cud is completely inappropriate for the mailing lists into which it is cross-ruminated. | | | O | Tim C. May (--|--) | / \

3 2

lists
by nobody＠nsm.htp.org 17 Dec '03

17 Dec '03

Can someone tell me if the toad cypherpunk list gets *all* the cypherpuink traffic? As I understand it there are three possible subscription points -- does one subscription cover all? Thanks in advance...

2 1

Re: Too many "Internet Conferences" in Washington (fwd)
by Jim Choate 17 Dec '03

17 Dec '03

Forwarded message: > Date: Wed, 7 Jan 1998 12:30:42 -0800 (PST) > From: Declan McCullagh <declan(a)well.com> > Subject: Re: Too many "Internet Conferences" in Washington > Attendance at this conference will be by invitation only. About 35 > individuals will represent a > variety of backgrounds and perspectives including the computing industry > (such as Internet service > providers, network administrators, and providers of "anonymizing" > services) the legal community, > professional societies, academic institutions, law enforcement agencies, > and other agencies of > government. This is the real fault with the conference mentality... How can anyone reasonably expect 35 people, invitation only or not, to have a clue about any aspect of the industry let alone some sort of birds eye view? I would wager that if we took the top 35 ISP's in the US they couldn't come up with a cohesive expression of viewpoint that would have a lifetime measured in anything more than a few weeks. Pure hubris. ____________________________________________________________________ | | | Those who make peaceful revolution impossible will make | | violent revolution inevitable. | | | | John F. Kennedy | | | | | | _____ The Armadillo Group | | ,::////;::-. Austin, Tx. USA | | /:'///// ``::>/|/ http://www.ssz.com/ | | .', |||| `/( e\ | | -====~~mm-'`-```-mm --'- Jim Choate | | ravage(a)ssz.com | | 512-451-7087 | |____________________________________________________________________|

1 0

Debit-card program cancelled because of fraud [FWD]
by Steve Schear 17 Dec '03

17 Dec '03

Date: Sun, 28 Dec 1997 09:22:45 -0500 From: Steve Bellovin <smb(a)research.att.com> Subject: Debit-card program cancelled because of fraud According to the AP, Burns National Bank (Durango, CO) is cancelling its debit-card program because of fraud. The article is maddeningly incomplete about technical details. Apparently, the "hackers" (to quote the article) counterfeited plastic cards and "took account number sequences off software that resides on the Internet before encoding them in the magnetic strip on the back of the card." When the fraud was detected, some customers had new cards issued, with some unspecified extra security feature. It didn't work; within a month, the accounts were penetrated again. Three other banks have been victimized by a similar scheme. All four use the same debit card vendor; Burns blames the vendor for inadequate security, in some unspecified form. They're looking for a new supplier; until then, the entire program is being suspended. Losses to date -- which are apparently being absorbed by the banks -- total $300,000.

1 0