Rubyの数値クラスは基本的に Numeric のサブクラスだが、そうなっていなく隠れているものがある。それがopensslライブラリ内の OpenSSL::BN 。（他にもあるかもしれないけど）

OpenSSL内で利用される多倍長整数クラスです。

通常多倍長整数を利用するには Bignum を用いてください。

暗号化に利用する計算が目的のため、通常の整数クラスには無いメソッドがいくつか用意されている。そのひとつに剰余をとりながらの演算（合同算術）が挙げられる。

合同算術メソッドの一覧

通常の演算子 +, -, *, /¹, ** もあり Integer と混ぜて使えるが、それに加えて #mod_xxx というメソッドが用意されている。これらは引数に法（modulus）を指定する。

加算 : #mod_add
減算 : #mod_sub
乗算 : #mod_mul
累乗（冪剰余） : #mod_exp
自乗（平方剰余） : #mod_sqr
逆元（モジュラー逆数） : #mod_inverse

このうち冪剰余とモジュラー逆数は、自力で効率よく計算しようとするとアルゴリズムの知識がそれなりに必要になる。これを標準ライブラリに任せられるのは嬉しい。

なお、冪剰余についてはRuby2.5から Integer#pow でもできるようになった。モジュラー逆数は以前に自作してみたことがあるが、このクラスを知っていたらわざわざやらなかったかも。

冪剰余とフェルマーの小定理

a = 12345   # any integer
n = 6700417 # prime number

# OpenSSL::BN
require 'openssl'

a.to_bn.mod_exp(n, n).to_i #=> a % n

# Integer (built-in class)
a ** n % n  #=> NaN (warning: in a**b, b may be too big)
a.pow(n, n) #=> a % n

モジュラー逆数

63 * 27 % 100 == 1

# OpenSSL::BN
require 'openssl'

63.to_bn.mod_inverse(100).to_i #=> 27
64.to_bn.mod_inverse(100).to_i #=> OpenSSL::BNError: no inverse

# https://www.rubydoc.info/gems/numeric_inverse
require 'numeric_inverse'
using NumericInverse

63.inv      #=> (1/63)
63.inv(100) #=> 27
64.inv(100) #=> ArgumentError: modulus 100 is not coprime to 64

利用例：RSA暗号の復号の計算

最近計算する機会があったので、 OpenSSL::BN でもやってみる。主な変数は以下の通り。

公開鍵 (n, e) は誰でも手に入る
- n は2つの素数の積
- e は適当な数²（※満たすべき条件はある）
秘密鍵 (n, d) は鍵ペアの作成者しか知らない
- n は公開鍵と同じ³
- d は e と対になる数
m と c はそれぞれ平文と暗号文（を数値化したもの）
- m から c を求めるのが暗号化で、公開鍵によって誰でも可能
- c から m を求めるのが復号で、秘密鍵によって鍵ペアの作成者のみ可能
  - 秘密鍵の d を知らずに復号できたら暗号解読成功

Wikipedia英語版にある例で復号を試す。公開鍵しか知らない状態でも、 n を素因数分解した2つの素数がわかれば、秘密鍵を求められる。

require 'openssl'

n, e = 3233, 17 # public key (n, e)
c = 2790 # ciphertext

# discover that 3233 == 61 * 53
# --> get a private key (n, d)
l = [61 - 1, 53 - 1].inject(:lcm)
d = e.to_bn.mod_inverse(l).to_i #=> 413

# decrypt
m = c.to_bn.mod_exp(d, n).to_i #=> 65 (plaintext)

# encrypt again
c = m.to_bn.mod_exp(e, n).to_i #=> 2790 (ciphertext)

Integer#divmodに似た剰余付き除法。 ↩
実際の公開鍵では固定値 65537 (0x10001) になっていることが多い。 ↩
理論上は n だけでいいが、実際の秘密鍵には元となった2つの素数も記録されている。 ↩