googleapis_auth/lib/src/crypto/rsa.dart

// Copyright 2021 Google LLC
//
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file or at
// https://developers.google.com/open-source/licenses/bsd

// A small part is based on a JavaScript implementation of RSA by Tom Wu
// but re-written in dart.

import 'dart:typed_data';

import 'package:meta/meta.dart';

/// Represents integers obtained while creating a Public/Private key pair.
final class RSAPrivateKey {
  /// First prime number.
  final BigInt p;

  /// Second prime number.
  final BigInt q;

  /// Modulus for public and private keys. Satisfies `n=p*q`.
  final BigInt n;

  /// Public key exponent. Satisfies `d*e=1 mod phi(n)`.
  final BigInt e;

  /// Private key exponent. Satisfies `d*e=1 mod phi(n)`.
  final BigInt d;

  /// Different form of [p]. Satisfies `dmp1=d mod (p-1)`.
  final BigInt dmp1;

  /// Different form of [p]. Satisfies `dmq1=d mod (q-1)`.
  final BigInt dmq1;

  /// A coefficient which satisfies `coeff=q^-1 mod p`.
  final BigInt coeff;

  /// The number of bits used for the modulus. Usually 1024, 2048 or 4096 bits.
  int get bitLength => n.bitLength;

  RSAPrivateKey(
    this.n,
    this.e,
    this.d,
    this.p,
    this.q,
    this.dmp1,
    this.dmq1,
    this.coeff,
  );
}

/// Performs the private key operation (signing) on [bytes] with the private
/// [key].
///
/// Others who have access to the public key will be able to verify this
/// the result.
///
/// The [intendedLength] argument specifies the number of bytes in which the
/// result should be encoded. Zero bytes will be used for padding.
@internal
Uint8List rawSign(RSAPrivateKey key, List<int> bytes, int intendedLength) {
  final message = bytes2BigInt(bytes);
  final encryptedMessage = _encryptInteger(key, message);
  return integer2Bytes(encryptedMessage, intendedLength);
}

BigInt _encryptInteger(RSAPrivateKey key, BigInt x) {
  // The following is equivalent to `(x % key.n).modPow(key.d, key.n)` but is
  // much more efficient. It exploits the fact that we have dmp1/dmq1.
  var xp = (x % key.p).modPow(key.dmp1, key.p);
  final xq = (x % key.q).modPow(key.dmq1, key.q);
  while (xp < xq) {
    xp += key.p;
  }
  return ((((xp - xq) * key.coeff) % key.p) * key.q) + xq;
}

@internal
BigInt bytes2BigInt(List<int> bytes) {
  var number = BigInt.zero;
  for (var i = 0; i < bytes.length; i++) {
    number = (number << 8) | BigInt.from(bytes[i]);
  }
  return number;
}

@visibleForTesting
Uint8List integer2Bytes(BigInt integer, int intendedLength) {
  if (integer < BigInt.one) {
    throw ArgumentError('Only positive integers are supported.');
  }
  final bytes = Uint8List(intendedLength);
  for (var i = bytes.length - 1; i >= 0; i--) {
    bytes[i] = (integer & _bigIntFF).toInt();
    integer >>= 8;
  }
  return bytes;
}

final _bigIntFF = BigInt.from(0xff);