December 2003 - cypherpunks-legacy

Re[2]: ArcotSign (was Re: Does security depend on hardware?)
by jnbailly＠west.raytheon.com 17 Dec '03

17 Dec '03

Woah.... I hate to interject noise, but I have to comment. Maybe Bruce's reply WAS a bit curt and not terribly helpful. But it's better to just let it drop, and not resort to criticizing typos. I'm a member of this list in the hopes that I'll learn something. While it's true that I didn't learn anything from Bruce's reply, I don't think anyone gains anything from grammar/spelling corrections! *smile* Jacob ______________________________ Reply Separator _________________________________ Subject: Re: ArcotSign (was Re: Does security depend on hardware?) Author: proff(a)iq.org at mime Date: 9/22/98 10:40 AM > >the legitimate user has, excepting the 'remembered secret'. Or is > >there anything wrong with my logic? > > Yes. There is something wrong with you logic. > > Bruce > ********************************************************************** > Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098 There's something wrong with you grammer. Cheers, Julian. RFC-822-headers: Received: from CONVERSION-DAEMON by mail.hac.com (PMDF V5.1-12 #26580) id <0EZP00401AHMT4(a)mail.hac.com> for "jacob n bailly"@mime.mail.hac.com; Tue, 22 Sep 1998 12:37:00 -0700 (PDT) Received: from PROCESS-DAEMON by mail.hac.com (PMDF V5.1-12 #26580) id <0EZP00401AHJSC(a)mail.hac.com> for "jacob n bailly"@mime.mail.hac.com; Tue, 22 Sep 1998 12:36:58 -0700 (PDT) Received: from fw-tu05.hac.com by mail.hac.com (PMDF V5.1-12 #26580) with ESMTP id <0EZP0028FAHI2D(a)mail.hac.com> for "jacob n bailly"@mime.mail.hac.com; Tue, 22 Sep 1998 12:36:56 -0700 (PDT) Received: from toad.com ([140.174.2.1]) by fw-tu05.hac.com (8.9.0/8.9.0) with ESMTP id MAA16615 for <jnbailly(a)west.raytheon.com>; Tue, 22 Sep 1998 12:38:01 -0700 (MST) Received: (from majordom@localhost) by toad.com (8.7.5/8.7.3) id KAA03863 for coderpunks-outgoing; Tue, 22 Sep 1998 10:40:19 -0700 (PDT) Received: from iq.org (proff(a)frame-gw.iq.org [203.4.184.233]) by toad.com (8.7.5/8.7.3) with SMTP id KAA03857 for <coderpunks(a)toad.com>; Tue, 22 Sep 1998 10:40:13 -0700 (PDT) Received: (qmail 17488 invoked by uid 110); Tue, 22 Sep 1998 17:40:08 +0000 Date: Wed, 23 Sep 1998 03:40:08 +1000 (EST) From: proff(a)iq.org Subject: Re: ArcotSign (was Re: Does security depend on hardware?) In-reply-to: <4.0.2.19980922114142.00956610(a)mail.visi.com> Sender: owner-coderpunks(a)toad.com Message-id: <19980922174008.17487.qmail(a)iq.org> MIME-version: 1.0 X-Mailer: ELM [version 2.4ME+ PL28 (25)] Content-transfer-encoding: 7BIT Precedence: bulk

1 0

Child Bicycle Safety Site
by jal＠jb.com 17 Dec '03

17 Dec '03

Word has it that you ride a bicycle - and that's why you've received this piece of email. --------- You should visit this site if you ride a bike AND have a child: http://www.springfield-or.com/familytrends Tell someone else who rides with a child what you've seen. --------- If you wish to be removed from future mailings, please reply with the word "Remove" in the subject line. Thank you.

1 0

Re: Stego-empty hard drives... (fwd)
by Brian B. Riley 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- On 9/22/98 3:48 PM, Jim Choate (ravage(a)einstein.ssz.com) passed this wisdom: >When you're at that level you don't carry the data across the line >you get some Johnnie Mnemonic to do it for you or put it in a >diplomatic pouch... I think the real answer here, and totally in keeping with the KISS rule, has already been suggested. If you have sensitive data you keep it on a PCMCIA hard drive card and remove it when not in use (or a CD-R or a ZipDisk, though the PCMCIA hard drive does allow it to be a 'working' volume featuring speed and capacity that a Zip or a CD-R cannot offer). It can work as easily for a desktop as for a laptop. You can add to the security of this by using your platform of choice's flavor of Secure Drive, Cryptdisk, PGPDisk, etc. The ultimate stego is that the card is nowhere near the computer with the main hard drive and they don't bother looking beyond when the drive evaluation turns nothing up. If its trafficking in illicit data the "mule' shouldn't even be carrying a computer (or maybe only a Palm Pilot!) so the hounds have even less reason to be looking for comp[uter stuff on him. -----BEGIN PGP SIGNATURE----- Version: PGP for Personal Privacy 5.0 Charset: noconv iQEVAwUBNggY7j7r4fUXwraZAQG3swf8C3ypMG6EyI6t2I2LIpcwyV37Khv6Vm06 15HZ7rFOzrqwXG8RjDw4e99f5H76IG9FuDJUbUfJX0lS9aKtEaeeuSPUmtso8Au9 NrdTp3lHxMYJH9q+d8l1gVZWOnLQCjiJ7Ytd4LCmhmb3Ds58Sa41YoM71EFKZJkK AIBC2pmkRT1ido4uvtLc9qjPDf/jtLHVH17tMdBKCvn6R8jbLq4QHk6T0J9rJt1O +owC6R8YGpWjXPkIicsgfDD6qJiyyLLAMRX/1qWLVI+2CjeImhMsUGjafkq98x/B UU6bGq8B5m2aJmpVMqGFceuJe4mUTtqxLfYF/MlwLokib7ap8+EEZw== =A9fC -----END PGP SIGNATURE----- Brian B. Riley --> http://members.macconnect.com/~brianbr For PGP Keys <mailto:brianbr@together.net?subject=Get%20PGP%20Key> "First say to your self what you would be; then do what you have to do." Epictetus (35-135 A.D.)

1 0

Re: Stego-empty hard drives... (fwd)
by Brian B. Riley 17 Dec '03

17 Dec '03

On 9/22/98 1:43 PM, Jim Choate (ravage(a)einstein.ssz.com) passed this wisdom: >Forwarded message: > >> Date: Tue, 22 Sep 1998 11:07:34 -0500 >> From: Petro <petro(a)playboy.com> >> Subject: Re: Stego-empty hard drives... (fwd) > >> I don't know how hard this would be, but how about running a >> seperate memory check, and while those numbers are flashing on the screen, >> do the wait for imput? > >So hide the keyscan in the memory counter code. Would work externaly, would >probably not show up on TEMPEST. Since both the keyscan and the memory scan >are repetitive TEMPEST might have a problem telling them apart. Provided you >could get the keyscan in the same footprint as the mem check the BIOS >would not show up as anomolous in size. As long as they're not running >around doing checksums you'd be ok (I suspect). Don't most memory scans do a keyscan anyway? looking for an ESC to bypass the scan? So have it also check for something else to bring up your special routine. It should pass all but the most detailed signature analysis. Brian B. Riley --> http://members.macconnect.com/~brianbr For PGP Keys <mailto:brianbr@together.net?subject=Get%20PGP%20Key> "Give a man a fish and you have fed him for a day, but give him a case of dynamite and soon the village will be showered with mud and seaweed and unidentifiable chunks of fish." -Joe Chew

1 0

Re: Stego-empty hard drives... (fwd)
by Jim Choate 17 Dec '03

17 Dec '03

Forwarded message: > Subject: Re: Stego-empty hard drives... (fwd) > Date: Tue, 22 Sep 1998 18:04:28 -0400 > From: "Brian B. Riley" <brianbr(a)together.net> > Don't most memory scans do a keyscan anyway? looking for an ESC to > bypass the scan? Some do, some don't. A lot of new machines resolve those issues in the BIOS with a setting that allows you to choose between a couple of options at post. > So have it also check for something else to bring up > your special routine. It should pass all but the most detailed signature > analysis. Maybe, the fact that you've added an extra block of code in there to check for the additional keystroke would cause the cycle length of that section of ML to be slightly longer, probably no more than 30 - 40 clock cycles. If you're looking at the EM radiation that lengthening could show up. ____________________________________________________________________ The seeker is a finder. Ancient Persian Proverb The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage(a)ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------

1 0

advertisement
by befcorp＠mail.ios.net 17 Dec '03

17 Dec '03

561 540 4028 561 540 4028 E MAIL KING AND ASSOCIATES PUTS MONEY INTO YOUR POCKET!! OUR COMPANY HAS OVER 3 YEARS PROVEN E MAIL BLASTING EXPERIENCE! WORK SMARTER BY HAVING QUALIFIED PEOPLE PHONE YOU, ALREADY PREPARED TO BUY. PUT YOUR COLD CALLING DAYS TO AN END. TRY US OUT TODAY AND JUDGE THE RESULTS FOR YOURSELF! 10,000 E MAILS ARE ONLY $125.00 US. Do you only market your product or service geographically? Not a problem with E Mail King. We can target your e-mail broadcastes into the city of your choosing! FOR THOSE OF YOU WHO NEED MAILING CONTINOUSLY DONE, WE WILL E MAIL YOUR ADD TO 7500 DIFFERENT ADDRESSES DAILY MONDAY THROUGH FRIDAY MONTH AFTER MONTH FOR ONLY $250.00 PER MONTH. CALL TODAY FOR DETAILS ON THIS FANTASTIC OFFER!! IF YOU ALREADY HAVE YOUR OWN E MAIL SYSTEM, WHY NOT TRY OUR SUBCRIPTION SERVICE WHERE YOU WILL RECEIVE 50,000 FRESH GOOD E MAIL ADDRESSES EVERY MONTH FOR ONLY $90.00. ARE YOU INTERESTED IN BEING AN E MAIL KING RESELLER? PUT EVEN MORE MONEY INTO YOUR POCKET TODAY BY SIGNING UP WITH OUR PROGRAM TODAY!! IT DOES NOT COST ANYTHING TO JOIN!! We accept Visa, Mastercard or Cheque by Fax. James phone 561 540 4028 _________________________________________________________________ TO BE REMOVED FROM OUR LIST, email james456(a)indiasite.com and type in "remove" in the subject header or call (561)540 4028 our mailing address is EMAIL KING 1790 Bonhill Rd Mississauga Ontario Canada

1 0

respect due to anonymous (Re: CHALLENGE response (fwd)) (fwd)
by Jim Choate 17 Dec '03

17 Dec '03

Forwarded message: > Date: Tue, 22 Sep 1998 20:20:37 +0100 > From: Adam Back <aba(a)dcs.ex.ac.uk> > Subject: respect due to anonymous (Re: CHALLENGE response (fwd)) > Munge signatures!? He generated an RSA key pair to match the > pre-published signature based on generating primes of special form > and/or using multiple smaller primes to construct an n which he could > perform discrete logs in (plus a dead beef attack), and all you can > say is the above. You should take you hat off to anonymous. What he did is respectable. Is he the first? I doubt it. ____________________________________________________________________ The seeker is a finder. Ancient Persian Proverb The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage(a)ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------

1 0

public key problems
by bill payne 17 Dec '03

17 Dec '03

Tuesday 9/22/98 5:59 PM Smith http://www.softwar.net/softd.html I am reading http://www.softwar.net/mcc.html I scanned-in the attached letter from McNamara. Morales and I have been considering an appropriate response. Public key has cost NSA and the gov BIG BUCKs. Numerical analyst Richard Hanson worked in the same math group as Simmons, Brickell and Norris. http://www.vni.com/products/imsl/hanson.html Mike Norris, Hanson told me, designed the reciprocal approximation used for division. Hanson told me several days ago he knows what went wrong mathematically. Hanson told me that he is even thinking of writing an article about it. I WAS TOLD what went wrong electronically. By John Wisniewski. And FUNCTIONALLY by Ron Kulju. best bill NATIONAL SECURITY AGENCY FORT GEORGE G. MEADE, MARYLAND 20755-6000 Serial: J9343A-98 19 August 1998 Mr. William H. Payne 13015 Calle de Sandias Albuquerque, NM 87111 Dear Mr. Payne: This replies to your 15 May 1998 letter appealing the National Security Agency's (NSA) decision to deny your request for a fee waiver for your Freedom of Information Act request for invoices from various companies to NSA for payments for developing public key-related chips or Clipper chip-related hardware between January 1980 and February 1998. Your appeal was received in the Office of General Counsel on 29 May 1998. I have reviewed your 27 February 1998 request, the Office of Policy's 30 March 1998 response, and your appeal letter; and I have concluded that the fee waiver should not be granted. In reaching this decision, a number of factors were evaluated in light of the Act's purpose of promoting an informed citizenry. The key issue I considered in my review is whether disclosure of the information is likely to contribute to the pubic understanding of the operations or activities of the government. See 5 U.S.C. § 552 (a)(4XA)(iii). Implicit in this standard is a requirement to assess the nature of the information requested and whether it will likely be disseminated to the general public and will contribute to increased public understanding of the operations of the government. In order to support a fee waiver; the connection between furnishing the requested information and benefiting the public should be substantial. You have not indicated how you intend to disseminate any information which might be released; we assume that you intend to place the material on the Internet. Making information available by posting it on the Internet so that a segment of interested persons might seek access to it does not meet the burden of demonstrating with particularity that the information will significantly contribute to the understanding of the public at large. You have not demonstrated that you have the skills and knowledge to be able to compile, analyze, and turn the materials into a distinct work understandable to the general public. Accordingly, I have determined that the public interest is better served in this instance by requiring, rather than waiving, the fee assessment. This response may be construed as a denial of your appeal. Accordingly, you are hereby advised of your right to seek judicial review of my decision pursuant to 5 U.S.C. § 552(a)(4)B) in the United States District Court in the district in which you reside, in which you have your principal place of business, in which the Agency's records are situated (U.S. District Court of Maryland), or in the District of Columbia. As the Deputy Director of Policy explained to you, you have been placed in the"all other" category for fee purposes; this entitles you to 2 hours of search time and up to 100 pages free of charge. Your case file has been returned to the Office of Policy. Processing of your request has been suspended pending receipt of your certified check or money order made payable to the Treasurer of United States in the amount of $750.00. If you have any questions or wish to narrow your request in order to reduce fees, please contact the Office of Policy between 0830 and 1600 EST on 301-688-6527. If we do not hear from you within 30 days, we will assume you are not interested in pursuing this request. Sincerely, BARBARA A. McNAMARA Freedom of Information Act/Privacy Act Appeals Authority Friday February 27, 1998 3:15 PM By e-mail and US mail Lieutenant General Kenneth A Minihan, USAF Director, National Security Agency National Security Agency 9800 Savage Road Fort George G. Meade, MD 20755-6000 Dear General Minihan: Purposes of the letter are to 1 request information under the Freedom of Information Act 2 explore settlement possibilities of our current lawsuit. In about 1986 Sandia National Laboratories assigned me the task of design and construction of a Comprehensive Test Ban Treaty seismic data authenticator. In the initial stages of the project, Sandia cryptographer Gustavus Simmons attempted to convince both Sandia management and NSA employees Tom White, Mark Unkenholtz, and Ed Georgio that a form of public key authentication should replace NSA employee Ronald Benincasa's National Seismic Station/Unmaned Seismic Observatory 11-bit data authentication algorithm. My Sandia supervisor John Holovka and project leader H B [Jim] Durham ordered me to write a paper explaining public key cryptography. This paper, RSA ENCRYPTION, along with my SAND report describing my implementation of Benincasa's algorithm and filings in our lawsuit, now appear on Internet at http://www.jya.com/index.htm, click CRYPTOME, then OpEd, then http://www.jya.com/whprsa.htm. Sandia explored the merits of switching from Benincasa's algorithm to a public key-based authentication method suggested by Simmons. For Sandia's evaluation of the merits of public key, electronic tagging, and Bureau of Engraving and Printing projects , I bought for Sandia samples both the Cylink CY1024 and AT&T A & B two chip sets for modulo m arithmetic computations. NSA employee Tom White sent me a copy of the SECRET classified NSA report on IBM's hardware public key chip FIREFLY. I wrote in my tutorial paper RSA hardware computations The slow speed of software RSA computations plus the potential wide use prompted several companies to build chips which compute modular arithmetic to at least several hundred bits. Most of these chips "cascade" to compute with a larger number of bits. Corporations involved in building these chips are 1 IBM Firefly 2 AT&T 3 Motorola (apparently a three chip set) 4 Cylink Pittway-First alert 5 Sandia Labs (Algorithm M and predecessor chip) Details of the IBM chip is classified. AT&T as of July 1987 has not released details of their chip. Little information is available on the Motorola chip set. The Cylink chip is commercially available. Its price dropped from $1,500 to $600 each in June 1987. Data is transferred to and from the chip with serial shift register communication. The early Sandia chip was limited in speed. The replacement chip is cascadeable, communicates with 8 or 16 bits parallel, matches the speed of the Cylink chip, but is not out of fabrication. Rumors circulate that there is about an order of magnitude performance difference between some of these chips. These hardware chips improve exponentiation speed about 3 orders of magnitude over software implementation benchmarked on an Intel 8086 family microcomputer. Whitfield Diffie writes about both the Cylink and Sandia chips. And is quoted at http://www.aci.net/kalliste/nukearse.htm. Sandia had terrible luck with its public key chips. I reported SOME of the troubles to Electronic Engineering Times editor Loring Wirbel [http://techweb.cmp.com/eet/823/] on March 23, 1994. Dr. John Wisniewski was a supervisor at Sandia's Center for Radiation-hardened Microelectronics. Wisniewski was a graduate student at Washington State University in about 1975. I was a professor at WSU. Wisniewski knows all about the failing Sandia chips in the nuclear arsenal. I took notes on February 13, 1993. Wisniewski reviewed the problems again for me. 1 No quality initiative. Each chip lot had a different process. 2 Overall yield - 40-50%. Down to 10% after packaging. 3 Metalization problems. No planarization. No flow of glass. Couldn't use high temperature. Step coverage problems. Layed down over tension. 100% field returns over several years. 4 Sandia would store lots of parts for replacements. Sandia management made the decision to place low yield parts in the nuclear arsenal. Sandia must meet DOD schedules management reasoned. Hundreds of millions spent on CRM. Sandia must show productivity. Wisniewski told me that low yield chip test survivors are those whichthe tests failed to detect failures. Wisniewski will talk. 503-625-6408. Wisniewski now works for Intel in Oregon. Have Wisniewski tell you about the fire in the CRM clean room! Sandia supervisor Jerry Allen later told me it cost $300,000 each to remove Sandia's failing chips at Pantex from a nuclear bomb. NSA apparently is biased toward hardware implementations of cryptographic and authentication algorithms. As opposed to software implementation. NSA representatives and Sandia management decided not to use a public key authentication scheme for its CTBT seismic data authenticator because of all of the problems with implementing public key algorithms. But NSA surely has spent MUCH MONEY on public key chip implementations. NSA is promoting its Clipper crypto chips as described at http://cpsr.org/dox/clipper.html. And we get some information about technical specifications of NSA's Clipper chip at http://www.us.net/softwar/http://www.us.net/softwar/clip.html Clipper Chip Information MYK-78 CLIPPER CHIP ENCRYPTION/DECRYPTION ON A CHIP 1 micron double level metal CMOS technology 0.35 watts power 28 pin plastic leaded chip carrier (PLCC) package Transistor to transistor logic (TTL) interface Chip ID, family key and device unique key are installed at programming. Chip ID, family key and device unique key are installed at programming facility and are completely transparent to the user. Therefore, Under the provision of the Freedom of Information Act, 5 USC 552, I am requesting access to: 1 Copies of all invoices from A AT&T B Motorola C IBM D Sandia National Laboratories to NSA for payments for developing ANY public key-related chips between January 1, 1980 and February 27, 1998. 2 Copies of all invoices to NSA from ANY corporation involved in development of ANY Clipper chip-related hardware between January 1, 1980 and February 27, 1998. The public has a right to know how much NSA spent on TRYING monoploize the crypto business. If there are any fees for searching for, or copying, the records I have requested, please inform me before you fill the request. As you know, the Act permits you to reduce or waive the fees when the release of the information is considered as "primarily benefiting the public." I believe that this requests fits that category and I therefore ask that you waive any fees. If all or any part of this request is denied, please cite the specific exemption(s) which you think justifies your refusal to release the information and inform me of your agency's administrative appeal procedures available to me under the law. I would appreciate your handling this request as quickly as possible, and I look forward to hearing from you within 20 working days, as the law stipulates. With respect to our current FOIA lawsuit, I feel that we should settle this unfortunate matter. I see from your biography at http://www.nsa.gov:8080/ and http://www.nsa.gov:8080/dirnsa/dirnsa.html that you are 1979 Distinguished Graduate Master of Arts degree in National Security Affairs Naval Postgraduate School Monterey, California One of my former M.S. and Ph.D students in Computer Science, Ted Lewis, is currently the chairman of Computer Science at Naval Postgraduate School [http://www.friction-free-economy.com/] Small world. But I think that this emphasizes that WE SHOULD all be on the same side. Not engaged in a conflict in US federal court. Or on Internet. NSA attempts to withhold requested information are possibly unwise. In our wired world the aggrieved know what happened to them. [http://www.aci.net/kalliste/speccoll.htm] http://www.wpiran.org/, http://www.netlink.co.uk/users/impact/namir/namirm.html And moderates in Iran, [http://persia.org/khatami/biography.html] appear want settlement too. My family and I have been damaged by these crypto wars. I ask you that consider fair settlement of damages caused by the National Security Agency. I cannot find your e-mail address on Internet. Therefore I will forward the e-mail copy of this FOIA/settlement letter to Ray Kammer of NIST [http://www.nist.gov/] who along with the FBI [http://www.fbi.gov/, http://www.fbi.gov/fo/nyfo/nytwa.htmand] and NSA are trying to control the crypto business so that Kammer can possibly forward an e-mail copy of the FOIA/Settlement letter to you. Sincerely, bill William Payne 13015 Calle de Sandias Albuquerque, NM 87111 505-292-7037 [I am not reading e-mail]

1 0

Re: (99% noise) Stego-empty hard drives... (fwd)
by Jim Choate 17 Dec '03

17 Dec '03

Forwarded message: > Date: Tue, 22 Sep 1998 19:45:34 -0400 > From: Sunder <sunder(a)brainlink.com> > Subject: Re: (99% noise) Stego-empty hard drives... (fwd) > Jim Choate wrote: > > > Consider that at any given time there are only a few hundred BIOS'es, made > > from a few dozen base images, driving all the machines out there. The number > > of companies that develop their own BIOS in toto for in-house products is next > > to nil (I know of none). What they do is buy a license and then re-write the > > sections they need to. > > See: http://www.ping.be/bios/ for bioses and flash upgrades. Ok, so I went and looked. That particular page covers ONLY Award and AMI BIOS's. Every one of those *thousands* of machines have a BIOS which is about 90% cherry and built from only a few dozen base builds. It actualy supports my premise that despite the thousands of machines the base BIOS images that drive them are really not that large. > Come on guys, this is silly. Why the fuck would the UK tempest scan your > notebooks? Manufacturers produce new machines every month, each with modified > BIOSes for the features in their new notebooks, with hardware variations and > imperfection, with different power levels of batteries, different PC cards > installed, different CPU speeds, different options and other inconsistencies > you get a very difficult situation. And everyone one of them available publicly. You seriously think it's harder to keep up with the number of BIOS'es out there than say tracking the number of international phone calls in a year? > Your speculation that someone out there will tempest scan to see if you've > modded your notebook is silly. Are you just pissing against the wind, or do > you have knowledge that they actually do this? Not if it is only one or two, if it becomes a serious issue you bet they'll do it in a heartbeat. > You're forgetting your threat model and planning for a level that's beyond > demented paranoia. Your absolutely correct, they are paranoid. ____________________________________________________________________ The seeker is a finder. Ancient Persian Proverb The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage(a)ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------

1 0

Re: CHALLENGE response
by Anonymous 17 Dec '03

17 Dec '03

> What form are your primes (did you use Maurers idea to increase the > relative hardness of factoring compared to discrete log, or did you > just use more smaller primes?) How many primes have you used, and how > many CPU hours did it take to calculate the discrete log to discover e? N is the product of two primes, but each p-1 has about 16 small prime factors (about 25-35 bits) to allow calculating the discrete log efficiently. With this choice of primes it took about three hours to run the discrete log. > Also is the code for finding discrete logs given the prime > factorisation of the modulus available? Here you go. This uses cryptolib by Jack Lacy of AT&T (not to be confused with cryptlib by Peter Gutmann), available from ftp://ftp.funet.fi/pub/crypt/cryptography/libs/cryptolib_1.1.tar.gz /* Calculate discrete log using various algorithms */ /* Algorithms based on Handbook of Applied Cryptography by Menezes et al */ #include "libcrypt.h" /* Modular multiplication - m1*m2 mod n */ static void bigMultiplyN (BigInt m1, BigInt m2, BigInt n, BigInt result) { BigInt tmp = bigInit(0); bigMultiply (m1, m2, tmp); bigMod (tmp, n, result); freeBignum (tmp); } /* Modular addition, m1+m2 mod n */ static void bigAddN (BigInt m1, BigInt m2, BigInt n, BigInt result) { bigAdd (m1, m2, result); if (bigCompare (result, n) >= 0) bigSubtract (result, n, result); } /* Iterate the pollard rho. Modify x, a, b with next values */ static void prhoiter (BigInt base, BigInt val, BigInt mod, BigInt order, BigInt *x, BigInt *a, BigInt *b) { int xgroup; /* First decide what group x is in */ /* This is a cheat to be fast */ xgroup = ((unsigned)(*x)->num[0]+1) % 3; switch (xgroup) { case 0: bigMultiplyN (*x, val, mod, *x); bigAddN (*b, one, order, *b); break; case 1: bigMultiplyN (*x, *x, mod, *x); bigAddN (*a, *a, order, *a); bigAddN (*b, *b, order, *b); break; case 2: bigMultiplyN (*x, base, mod, *x); bigAddN (*a, one, order, *a); break; } } /* Pollard rho algorithm for discrete log */ BigInt pollardrho (BigInt base, BigInt val, BigInt mod, BigInt order) { BigInt x = bigInit(1), a = bigInit(0), b = bigInit(0), x2 = bigInit(1), a2 = bigInit(0), b2 = bigInit(0); int cnt = 0; for ( ; ; ) { prhoiter (base, val, mod, order, &x, &a, &b); prhoiter (base, val, mod, order, &x2, &a2, &b2); prhoiter (base, val, mod, order, &x2, &a2, &b2); if (bigCompare (x, x2) == 0) break; if (++cnt % 1000 == 0) { printf ("%d\r", cnt); fflush (stdout); } } if (cnt >= 1000) printf ("\n"); if (bigCompare (b, b2) < 0) bigAdd (order, b, b); bigSubtract (b, b2, b); if (bigCompare (a2, a) < 0) bigAdd (order, a2, a2); bigSubtract (a2, a, a); if (bigCompare (b, zero) == 0) { printf ("Pollard rho failed\n"); exit (1); } getInverse (b, order, b2); bigMultiplyN (a, b2, order, a); return a; } /* * Do the CRT with multiple congruences. congs are the values that the * answer should be congruent to, mods are the moduli for each congruence. * n tells how many in each array. */ static BigInt crtmult (BigInt congs[], BigInt mods[], int n) { int i; BigInt prod = bigInit(0); BigInt prod1 = bigInit(0); BigInt sum = bigInit(0); BigInt quot = bigInit(0); BigInt rem = bigInit(0); BigInt dum = bigInit(0); BigInt inv = bigInit(0); BigInt term = bigInit(0); /* Compute product of moduli */ bigCopy (one, prod); for (i=0; i<n; ++i) { bigMultiply (prod, mods[i], prod1); bigCopy (prod1, prod); } for (i=0; i<n; ++i) { bigDivide (prod, mods[i], quot, dum); bigDivide (quot, mods[i], dum, rem); getInverse (rem, mods[i], inv); bigMultiplyN (congs[i], quot, prod, term); bigMultiplyN (term, inv, prod, term); bigAddN (term, sum, prod, sum); } return sum; } /* Pohlig-Hellman discrete log algorithm for composites */ /* Return the exponent such that base^exponent == val modulo mod. */ /* Group order is product of factors[], of which there are n */ /* Assume each factor is to the first power */ BigInt phlog (BigInt base, BigInt val, BigInt mod, BigInt factors[], int n) { BigInt prod = bigInit(0), prod1 = bigInit(0), exp = bigInit(0), dum = bigInit(0), b = bigInit(0), v = bigInit(0); BigInt *dlogs; BigInt dl; int i; dlogs = (BigInt *) malloc (n * sizeof (BigInt)); /* Compute product of factors to get group order */ bigCopy (one, prod); for (i=0; i<n; ++i) { bigMultiply (prod, factors[i], prod1); bigCopy (prod1, prod); } /* Sanity check */ bigPow (base, prod, mod, b); if (bigCompare (b, one) != 0) { printf ("Inconsistency in group order on b\n"); fBigPrint (b, stdout); } bigPow (val, prod, mod, v); if (bigCompare (v, one) != 0) { printf ("Inconsistency in group order on v\n"); fBigPrint (v, stdout); } for (i=0; i<n; ++i) { bigDivide (prod, factors[i], exp, dum); bigPow (base, exp, mod, b); bigPow (val, exp, mod, v); printf ("Trying dlog with factor: "); fBigPrint (factors[i], stdout); printf ("b: "); fBigPrint (b, stdout); printf ("v: "); fBigPrint (v, stdout); /* Special case for 2, pollardrho doesn't work too well on it */ if (bigCompare (factors[i], two) == 0) { if (bigCompare (b, v) == 0) { dlogs[i] = bigInit(1); } else if (bigCompare (v, one) == 0) { dlogs[i] = bigInit(0); } else { printf ("Inconsistent b, v for factor == 2\n"); exit (1); } } else { /* Now find log of v mod b, has group order factors[i] */ dlogs[i] = pollardrho (b, v, mod, factors[i]); } printf ("dl: "); fBigPrint (dlogs[i], stdout); bigPow (b, dlogs[i], mod, b); if (bigCompare (b, v) != 0) { printf ("Error in discrete log calc!\n"); exit (1); } } /* Combine results with CRT */ dl = crtmult (dlogs, factors, n); return dl; }

1 0