outer@utcsri.UUCP (Richard Outerbridge) (01/02/87)
From the Report On Business section of the >Globe and Mail<, Thursday, January 1, 1987, page B5: Coding chip devised in Waterloo by David Helwig Special to The Globe and Mail Three professors from the University of Waterloo are preparing to market a microchip that ensures the privacy of digitized information. Gordon Agnew of the university's department of electrical engineering, and mathematicians Ron Mullin and Scot Vanstone, have joined with graduate student Ivan Onyzschuk to form Cryptech Inc. of Waterloo, Ontario. The company's device, known as a public key cryptosystem, has been produced in prototype form and should be ready for marketing by this summer, Mr. Vanstone said. The patented system is designed to secure computer data banks, electronic mail and digital telephone communications. It is simpler and many times faster than rival public key systems expected to become available soon, the company said. Conventional cryptographic systems use an electronic "key" to lock messages so that they can only be read by people who have a matching key. Public key systems have two keys - one for encrypting the message and another for decrypting it. The encrypting key can be made public by publishing it in a directory, but the decryption key is kept on a microchip possessed only by the owner. It is virtually impossible for an outsider to break the decrypting key, which consists of a binary string of more than 1,000 characters, Mr. Vanstone said. "It would take more than a billion years, working with the fastest computers available, to break just one key," he said. Banks could use the technology to ensure the authenticity of messages. It can produce digital "signatures" that cannot be forged and could be used for electronic processing of contracts and financial transactions, the company said. Microchips containing the Cryptech system will be made by Calmos Systems Inc. of Ottawa. Cryptech is being established with assistance from Robert Nally, the University of Waterloo's commercial development officer. The university will get royalties on sales of the chips. --- 30 --- -- Richard Outerbridge <outer@utcsri.UUCP> (416) 961-4757 Payload Deliveries: N 43 39'36", W 79 23'42", Elev. 106.47m.
dgc@CS.UCLA.EDU (01/02/87)
A Silicon Valley Company has a (very fast) chip implementation of
exponentiation (mod m) currently available. It supports the standard
public key crypto-algorithms which involve exponentiation including RSA.
The company is
Cylink
920 West Fremont Avenue
Sunnyvale, CA 94087
dgc
David G. Cantor
Internet: dgc@cs.ucla.edu
UUCP: ...!{ihnp4, randvax, sdcrdcf, ucbvax}!ucla-cs!dgcjbn@glacier.STANFORD.EDU (John B. Nagle) (01/02/87)
Is the patent out in any country yet? I'm interested in seeing how
it works. A patent number for any country would be appreciated. In
any case, these things can't be considered secure until they've stood
considerable scrutiny. Always remember Friedman's remark, "No new cypher
is worth looking at unless it comes from someone who has already broken a very
difficult one."
The big problem with public key systems is that one needs some
suitable function whose inverse is enormously harder to compute than the
function itself. The two functions most discussed to date are the knapsack
problem and the factorization of large numbers, and advances in mathematics
have made both problems much more tractible in the last few years. If
someone has a new function, it may be a significant step forward. Or
it may not. One would like a problem with a provable lower bound, but the
theory of lower bounds is very weak as yet.
With the advent of good, fast, modem technogies, and good voice
digitization and compression schemes, the use of digital encryption for
voice over voice-grade lines without serious loss of quality is already
possible. If this new scheme works, one could produce secure telephones
for consumer use which would automatically exchange public keys at startup
and then go to encrypted digital mode when talking to another of their
own kind. This sounds expensive and complicated, but it will eventually
come down to one chip with a small number of pins.
This has definite product potential. Let's hear more details about
the technology.
John Nagle
John Naglegwyn@brl-smoke.ARPA (Doug Gwyn ) (01/07/87)
- It is virtually impossible for an outsider to break the - decrypting key, which consists of a binary string of more than 1,000 - characters, Mr. Vanstone said. - "It would take more than a billion years, working with the - fastest computers available, to break just one key," he said. I hope it is obvious to most readers of this newsgroup that the above claim is bullshit. A similar argument would lead to the claim that Rubik's cube would take forever to solve. I personally have broken cryptosystems with longer keys. There is more to cryptosystem strength than key length.
jewett@hpl-opus.HP.COM (Bob Jewett) (01/08/87)
> / sci.crypt / gwyn@brl-smoke.ARPA (Doug Gwyn ) / 8:56 am Jan 7, 1987 / > - It is virtually impossible for an outsider to break the > - decrypting key, which consists of a binary string of more than 1,000 > - characters, Mr. Vanstone said. > - "It would take more than a billion years, working with the > - fastest computers available, to break just one key," he said. > > I hope it is obvious to most readers of this newsgroup that > the above claim is bullshit. Pretty strong statement, Doug. Let's look a little closer... If they use RSA, and the product number (public key) is 1000 bits long, we can ask how log it would take to factor the public key, or alternatively, how much it would cost. It presently costs about US$100000 to factor a 100 digit number. The cost increases by a factor of ten for each ten digits. 1000 bits is 300 digits, so the cost of factoring the public key would be US$10000000000000000000000000. I think that's enough to deter even the NSA. For a Cray 2, assuming a cost of operation of US$10Meg per year, this works out to 10^18 years. This is > 1 billion. Of course there are some hazy points. Do they use RSA, are there fast methods of breaking RSA (or factoring), is "1000 characters" actually 1000 bits, is my cost estimate and scaling formula correct, etc? The point is that Mr. Vanstone's statement, while unclear as quoted, is not unreasonable.
srt@duke.UUCP (Stephen R. Tate) (01/09/87)
In article <5490@brl-smoke.ARPA>, gwyn@brl-smoke.ARPA (Doug Gwyn ) writes: > - It is virtually impossible for an outsider to break the > - decrypting key, which consists of a binary string of more than 1,000 > - characters, Mr. Vanstone said. > - "It would take more than a billion years, working with the > - fastest computers available, to break just one key," he said. > > I hope it is obvious to most readers of this newsgroup that > the above claim is bullshit. A similar argument would lead > to the claim that Rubik's cube would take forever to solve. > > I personally have broken cryptosystems with longer keys. > There is more to cryptosystem strength than key length. I think everybody realizes that, and actually it is your notice that is bullshit. The original posting (which you even quoted) draws no comparison between key length and time to break the key. They are two different statements in different paragraphs. The way I read this is similar to the way I would read a statement on, say, the RSA protocol. Namely, breaking the RSA protocol has the same complexity as factoring a very large number. The fastest computer available today would take several billion years to factor such a large number, giving the security of the system. Clearly, nobody would consider an attempt at trying *all* keys (which would take considerably longer than a billion years for such a large key) as you seem to imply (with the statement about Rubik's Cube). -- Steve Tate UUCP: ..!{ihnp4,decvax}!duke!srt CSNET: srt@duke ARPA: srt%duke@csnet-relay
devine@vianet.UUCP (Bob Devine) (01/09/87)
> It is virtually impossible for an outsider to break the > encrypting key, which consists of a binary string of more than 1,000 > characters, Mr. Vanstone said. > "It would take more than a billion years, working with the > fastest computers available, to break just one key," he said. Ok if I believe the assertion that it is impossible for an outsider to break the key (absolute security? right...), why, then I'll just bribe an insider! Startling new idea isn't it :-) Bob Devine
henry@utzoo.UUCP (Henry Spencer) (01/11/87)
> - "It would take more than a billion years, working with the > - fastest computers available, to break just one key," he said. > > I hope it is obvious to most readers of this newsgroup that > the above claim is bullshit... It's a standard claim by the inventors of wonderful new cryptosystems, in fact. In one sense, you can claim that even solving a monoalphabetic substitution would take 26! (about 400000000000000000000000000) trials. In fact, a bright 12-year-old with an interest in the subject can break one in an hour, given a reasonable amount of input text. The fundamental fallacy is the assumption that a cryptanalyst tries and discards one key at a time, when in fact he discards entire classes of keys at a time. A minute's attention to a frequency chart of a text encrypted with a monoalphabetic substitution will eliminate 99.999...% of those 26! possible keys at once. "Work smart, not hard." -- Henry Spencer @ U of Toronto Zoology {allegra,ihnp4,decvax,pyramid}!utzoo!henry
karl@haddock.UUCP (Karl Heuer) (01/12/87)
In article <117@vianet.UUCP> devine@vianet.UUCP (Bob Devine) writes: >[If it is impossible for an outsider to break the key], why, then I'll just >bribe an insider! Startling new idea isn't it :-) I've heard that was the problem with the Great Wall of China. Incredible accomplishment (visible from the Moon?), but the enemy bribed a gatekeeper.
mouse@mcgill-vision.UUCP (der Mouse) (01/20/87)
>> [it is "virtually impossible" to break a certain system] > Ok if I believe the assertion that it is impossible for an outsider > to break the key (absolute security? right...), why, then I'll just > bribe an insider! Startling new idea isn't it :-) Right. People are often the weakest link in a security system. Assuming, that is that there *is* an insider who knows the key. If they were smart, there is no such person. (They killed him as soon as he typed in the numbers....:-) A box could have, let us say, a cosmic-ray detector which it uses to generate large numbers, then maybe it counds by twos until it finds primes. (No flames on details please, I just want to show the idea is feasible.) der Mouse USA: {ihnp4,decvax,akgua,utzoo,etc}!utcsri!mcgill-vision!mouse think!mosart!mcgill-vision!mouse Europe: mcvax!decvax!utcsri!mcgill-vision!mouse ARPAnet: think!mosart!mcgill-vision!mouse@harvard.harvard.edu
sewilco@mecc.MECC.COM (Scot E. Wilcoxon) (01/23/87)
In article <602@mcgill-vision.UUCP> mouse@mcgill-vision.UUCP (der Mouse) writes: >>...bribe an insider! Startling new idea isn't it :-) >Right. People are often the weakest link in a security system. > >Assuming, that is that there *is* an insider who knows the key. If >they were smart, there is no such person. (They killed him as soon as >he typed in the numbers....:-) A box could have, let us say, a >cosmic-ray detector which it uses to generate large numbers, then maybe >it counds by twos until it finds primes. (No flames on details please, >I just want to show the idea is feasible.) OK. Bribe an insider to learn the technology and the time when keys are generated. At that time, a nuclear accelerator in a truck on the street outside will create a modulated signal for the key generator's detector. Noise might interfere with the signal, but the technique might skew the keys in a known way. [OK, let's not get into a counteratomic spoofing discussion] Any method which uses an external signal depends upon secrecy of the algorithm. If an outsider can't spoof the signal, he might be able to listen to it and duplicate the key generation. With a radio receiver as the detector, the above could be called "electronic warfare". But in the atomic field, "nuclear warfare" has another meaning, although that also messes up detectors :-) -- Scot E. Wilcoxon Minn Ed Comp Corp {quest,dayton,meccts}!mecc!sewilco (612)481-3507 sewilco@MECC.COM ihnp4!meccts!mecc!sewilco "Who's that lurking over there? Is that Merv Griffin?"
devine@vianet.UUCP (Bob Devine) (01/23/87)
> >> [it is "virtually impossible" to break a certain system] > > Ok if I believe the assertion that it is impossible for an outsider > > to break the key (absolute security? right...), why, then I'll just > > bribe an insider! Startling new idea isn't it :-) > [What if] there is no such person. (They killed him as soon as > he typed in the numbers....:-) It then might be possible to use the third part of system security -- denial of service (theft of information and creation of false information are the other two). In a statement to the owners of a system, we would say "Alright! Give us all your encrypted information or da computer gets it!". Such statements carry more weight if you have arranged to aim a rather nasty weapon in the general direction of the computer beforehand... This approach may not bring the expected result if you try it against people who have even nastier weapons aimed at you. Bob Devine