keygen_test.go

     1  // Copyright 2024 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package rsa
     6  
     7  import (
     8  	"bufio"
     9  	"crypto/internal/fips140/bigmod"
    10  	"encoding/hex"
    11  	"fmt"
    12  	"math/big"
    13  	"os"
    14  	"strings"
    15  	"testing"
    16  )
    17  
    18  func TestMillerRabin(t *testing.T) {
    19  	f, err := os.Open("testdata/miller_rabin_tests.txt")
    20  	if err != nil {
    21  		t.Fatal(err)
    22  	}
    23  
    24  	var expected bool
    25  	var W, B string
    26  	var lineNum int
    27  	scanner := bufio.NewScanner(f)
    28  	for scanner.Scan() {
    29  		lineNum++
    30  		line := scanner.Text()
    31  		if len(line) == 0 || line[0] == '#' {
    32  			continue
    33  		}
    34  
    35  		k, v, _ := strings.Cut(line, " = ")
    36  		switch k {
    37  		case "Result":
    38  			switch v {
    39  			case "Composite":
    40  				expected = millerRabinCOMPOSITE
    41  			case "PossiblyPrime":
    42  				expected = millerRabinPOSSIBLYPRIME
    43  			default:
    44  				t.Fatalf("unknown result %q on line %d", v, lineNum)
    45  			}
    46  		case "W":
    47  			W = v
    48  		case "B":
    49  			B = v
    50  
    51  			t.Run(fmt.Sprintf("line %d", lineNum), func(t *testing.T) {
    52  				if len(W)%2 != 0 {
    53  					W = "0" + W
    54  				}
    55  				for len(B) < len(W) {
    56  					B = "0" + B
    57  				}
    58  
    59  				// Our Miller-Rabin assumes candidates are 3 mod 4.
    60  				w := decodeHex(t, W)
    61  				if len(w) == 0 || w[len(w)-1]%4 != 3 {
    62  					t.Skip("skipping test with W not congruent to 3 mod 4")
    63  				}
    64  
    65  				mr, err := millerRabinSetup(w)
    66  				if err != nil {
    67  					t.Logf("W = %s", W)
    68  					t.Logf("B = %s", B)
    69  					t.Fatalf("failed to set up Miller-Rabin test: %v", err)
    70  				}
    71  
    72  				result, err := millerRabinIteration(mr, decodeHex(t, B))
    73  				if err != nil {
    74  					t.Logf("W = %s", W)
    75  					t.Logf("B = %s", B)
    76  					t.Fatalf("failed to run Miller-Rabin test: %v", err)
    77  				}
    78  
    79  				if result != expected {
    80  					t.Logf("W = %s", W)
    81  					t.Logf("B = %s", B)
    82  					t.Fatalf("unexpected result: got %v, want %v", result, expected)
    83  				}
    84  			})
    85  		default:
    86  			t.Fatalf("unknown key %q on line %d", k, lineNum)
    87  		}
    88  	}
    89  	if err := scanner.Err(); err != nil {
    90  		t.Fatal(err)
    91  	}
    92  }
    93  
    94  func TestTotient(t *testing.T) {
    95  	f, err := os.Open("testdata/gcd_lcm_tests.txt")
    96  	if err != nil {
    97  		t.Fatal(err)
    98  	}
    99  
   100  	var GCD, A, B, LCM string
   101  	var lineNum int
   102  	scanner := bufio.NewScanner(f)
   103  	for scanner.Scan() {
   104  		lineNum++
   105  		line := scanner.Text()
   106  		if len(line) == 0 || line[0] == '#' {
   107  			continue
   108  		}
   109  
   110  		k, v, _ := strings.Cut(line, " = ")
   111  		switch k {
   112  		case "GCD":
   113  			GCD = v
   114  		case "A":
   115  			A = v
   116  		case "B":
   117  			B = v
   118  		case "LCM":
   119  			LCM = v
   120  
   121  			t.Run(fmt.Sprintf("line %d", lineNum), func(t *testing.T) {
   122  				if A == "0" || B == "0" {
   123  					t.Skip("skipping test with zero input")
   124  				}
   125  				if LCM == "1" {
   126  					t.Skip("skipping test with LCM=1")
   127  				}
   128  
   129  				p, _ := bigmod.NewModulus(addOne(decodeHex(t, A)))
   130  				a, _ := bigmod.NewNat().SetBytes(decodeHex(t, A), p)
   131  				q, _ := bigmod.NewModulus(addOne(decodeHex(t, B)))
   132  				b, _ := bigmod.NewNat().SetBytes(decodeHex(t, B), q)
   133  
   134  				gcd, err := bigmod.NewNat().GCDVarTime(a, b)
   135  				// GCD doesn't work if a and b are both even, but LCM handles it.
   136  				if err == nil {
   137  					if got := strings.TrimLeft(hex.EncodeToString(gcd.Bytes(p)), "0"); got != GCD {
   138  						t.Fatalf("unexpected GCD: got %s, want %s", got, GCD)
   139  					}
   140  				}
   141  
   142  				// a and b must be even and a/2 and b/2 must be odd for totient to work.
   143  				if a.Bits()[0]%4 != 2 || b.Bits()[0]%4 != 2 {
   144  					t.Skip("skipping test with invalid input for totient")
   145  				}
   146  
   147  				lcm, err := totient(p, q)
   148  				if new(big.Int).SetBytes(decodeHex(t, GCD)).BitLen() > 32 {
   149  					if err != errDivisorTooLarge {
   150  						t.Fatalf("expected divisor too large error, got %v", err)
   151  					}
   152  					t.Skip("GCD too large")
   153  				}
   154  				if err != nil {
   155  					t.Fatalf("failed to calculate totient: %v", err)
   156  				}
   157  				if got := strings.TrimLeft(hex.EncodeToString(lcm.Nat().Bytes(lcm)), "0"); got != LCM {
   158  					t.Fatalf("unexpected LCM: got %s, want %s", got, LCM)
   159  				}
   160  			})
   161  		default:
   162  			t.Fatalf("unknown key %q on line %d", k, lineNum)
   163  		}
   164  	}
   165  	if err := scanner.Err(); err != nil {
   166  		t.Fatal(err)
   167  	}
   168  }
   169  
   170  func addOne(b []byte) []byte {
   171  	x := new(big.Int).SetBytes(b)
   172  	x.Add(x, big.NewInt(1))
   173  	return x.Bytes()
   174  }
   175  
   176  func decodeHex(t *testing.T, s string) []byte {
   177  	t.Helper()
   178  	if len(s)%2 != 0 {
   179  		s = "0" + s
   180  	}
   181  	b, err := hex.DecodeString(s)
   182  	if err != nil {
   183  		t.Fatalf("failed to decode hex %q: %v", s, err)
   184  	}
   185  	return b
   186  }
   187
View as plain text