Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Paul Rubin Newsgroups: comp.lang.forth Subject: Re: string-stack.4th Date: Mon, 17 Apr 2017 16:57:44 -0700 Organization: A noiseless patient Spider Lines: 31 Message-ID: <87d1cah9jb.fsf@nightsong.com> References: <2687ca1c-6423-4ffd-a2d7-707da416569d@googlegroups.com> <4bce5098-0505-41b7-8bf6-4263846d3bb2@googlegroups.com> <41c816a2-6258-4e2d-8693-2cf2a7cd8d6c@googlegroups.com> <562e4faf-9de1-4f9e-b0b2-ef25e97f222b@googlegroups.com> <3db60aeb-6eb3-4445-bef2-7fd241c8b89c@googlegroups.com> <87tw5no388.fsf@nightsong.com> <87y3uyhjvw.fsf@nightsong.com> <9769c33e-1d5b-46a2-9404-e95f25151814@googlegroups.com> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: mx02.eternal-september.org; posting-host="2d496fb5cac5cc5b7a9fe9f8747e0f1d"; logging-data="22580"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/dwy3RDH1kPsPOfByx5QvW" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) Cancel-Lock: sha1:qX7m0NIxTeZVkw4dqYYuHs4Vmi8= sha1:keO1i66mQrTKo1/YtB1rrnmfLD8= Xref: csiph.com comp.lang.forth:57513 lehs writes: > GForth Android runs on 1.6 GHz Rockchip RK3066 > The others on 1.6 GHz Celeron both dual core. Pretty good. On the original IBM PC, with a C implementation, this calculation apparently would have taken minutes. > I've no idea how to code public-key cryptography or why I would need it. Basically say I want to send you a secret message. You pick two random primes p and q and compute the product N=pq and send me N. Other people (including me) can't find p and q from N, under the assumption that factoring numbers of this size is computationally intractable. Now you figure out the totient phi(N)=(p-1)*(q-1), which is the size of Z*(N), the group of numbers coprime to N. Since you can find p and q from phi(N), that means finding phi(N) is as hard as factoring, so N won't leak info about phi(N) more than it does about the factors. Now use the extended Euclidean algorithm to find a number d such that d*3 == 1 (mod phi(N)) and keep d secret. I take my message M and send you M**3 mod N. You use d to find M**(3*d) mod N, but since 3*d-1 is a multiple of phi(N), that means that M**(3*d) mod N is just M. So without telling me anything secret, on a channel where anyone can be listening, you've sent me info that lets me send you an encrypted message. This is public-key cryptography and the above algorithm is called "RSA" after its inventors Rivest, Shamir, and Adelman. Obviously there are a lot of practical details glossed over above, but basically it's all about how fast you can do modular exponentials in a group of size around 2**1000. That's why I wanted that timing.