I was an idiot and was thinking that a small base didn't matter
because the exponentiation would quickly make the number the same size
as the modulus. But, of course, the small base continues to make
multiplications unrealistically cheap throughout the computation.

R=golang-dev, r
CC=golang-dev
https://golang.org/cl/6649048

crypto/rsa: only enforce that de ≡ 1 mod |(ℤ/nℤ)*| in order to load private keys generated by GnuTLS.

Previously we checked that de ≡ 1 mod φ(n). Since φ(n) is a multiple
of |(ℤ/nℤ)*|, this encompassed the new check, but it was too strict as
keys generated by GnuTLS would be rejected when gcd(p-1,q-1)≠1.

(Also updated the error strings in crypto/rsa to contain the package name, which some were missing.)

R=golang-dev, r
CC=golang-dev
https://golang.org/cl/5867043

R=rsc
CC=golang-dev
https://golang.org/cl/5358041

With full multi-prime support we can support version 1 PKCS#1 private
keys. This means exporting all the members of rsa.PrivateKey, thus
making the API a little messy. However there has already been another
request to export this so it seems to be something that's needed.

Over time, rsa.GenerateMultiPrimeKey will replace rsa.GenerateKey, but
I need to work on the prime balance first because we're no longer
generating primes which are a multiples of 8 bits.

Fixes #987.

R=rsc
CC=golang-dev
https://golang.org/cl/4378046

R=golang-dev, rsc1
CC=golang-dev
https://golang.org/cl/4365041

The CRT is symmetrical in the case of two variables and I picked a
different form from PKCS#1.

R=golang-dev, rsc1
CC=golang-dev
https://golang.org/cl/4381041

This speeds up private key operations by 3.5x (for a 2048-bit
modulus).

R=golang-dev, r, rsc1
CC=golang-dev
https://golang.org/cl/4348053

These are the top runners.  More to come.
Also print two digits of timing info under -test.v.

R=rsc
CC=golang-dev
https://golang.org/cl/4317044

PKCS#1 v2.1 section 7.1.1 says that the result of an OAEP encryption
is "an octet string of length $k$". Since we didn't left-pad the
result it was previously possible for the result to be smaller when
the most-significant byte was zero.

Fixes #1519.

R=rsc
CC=golang-dev
https://golang.org/cl/4175059

R=r, rsc
CC=golang-dev
https://golang.org/cl/2662041

R=rsc, brainman
CC=golang-dev
https://golang.org/cl/1773041

Previously we would require safe primes for our RSA key generation.
Since this took rather a long time, this removes the requirement that
the primes be safe.

OpenSSL doesn't use safe primes for RSA key generation either
(openssl-0.9.8l/crypto/rsa/rsa_gen.c:122)

Fixes #649.

R=rsc
CC=golang-dev
https://golang.org/cl/253041

                  parsing and printing to new syntax.

                  Use -oldparser to parse the old syntax,
                  use -oldprinter to print the old syntax.

               2) Change default gofmt formatting settings
                  to use tabs for indentation only and to use
                  spaces for alignment. This will make the code
                  alignment insensitive to an editor's tabwidth.

                  Use -spaces=false to use tabs for alignment.

               3) Manually changed src/exp/parser/parser_test.go
                  so that it doesn't try to parse the parser's
                  source files using the old syntax (they have
                  new syntax now).

               4) gofmt -w src misc test/bench

	       1st set of files.

R=rsc
CC=agl, golang-dev, iant, ken2, r
https://golang.org/cl/180047

We are dealing with the multiplicative group ℤ/pqℤ. Multiples of
either p or q are not members of the group since they cannot have an
inverse. (Such numbers are 0 in the subgroup ℤ/pℤ.)

With p and q of typical size (> 512 bits), the probability of a random
blind [1..pq-1] being a multiple of p or q is negligible. However, in
the unit tests, much smaller sizes are used and the event could occur.

This change checks the result of the ext GCD and deals with this case.

It also increases the size of p and q in the unit test as a large
number of the keys selected were p, q = 227,169.

R=rsc
CC=golang-dev
https://golang.org/cl/154141

TBR=agl1
CC=golang-dev
https://golang.org/cl/154065

  Turn methods that don't store the result in their receiver into
    functions in order to preserve the convention.
  Re-jig Exp and Div by moving their guts into nat.go.
  Add ProbablyPrime to perform Miller-Rabin primality tests.
crypto/rsa: reenable key generation since we now have ProbablyPrime.

R=gri
CC=go-dev
http://codereview.prom.corp.google.com/1024038

R=rsc, r
http://go/go-review/1025029

Make RSA and X509 build by using big. (This involves commenting out
key generation for now since I haven't written Miller-Rabin in big
yet.)

Add entries to the Makefile.

R=rsc
CC=go-dev
http://go/go-review/1022005

R=rsc
CC=go-dev
http://go/go-review/1018020

R=go-dev
APPROVED=rsc
DELTA=407  (400 added, 0 deleted, 7 changed)
OCL=36007
CL=36146

R=r
APPROVED=r
DELTA=16  (0 added, 15 deleted, 1 changed)
OCL=35976
CL=35978

R=rsc
APPROVED=rsc
DELTA=734  (734 added, 0 deleted, 0 changed)
OCL=35738
CL=35879