Rubyの数値クラスは基本的に Numeric のサブクラスだが、そうなっていなく隠れているものがある。それがopensslライブラリ内の OpenSSL::BN 。（他にもあるかもしれないけど）
OpenSSL内で利用される多倍長整数クラスです。
通常多倍長整数を利用するには
Bignumを用いてください。
暗号化に利用する計算が目的のため、通常の整数クラスには無いメソッドがいくつか用意されている。そのひとつに剰余をとりながらの演算（合同算術）が挙げられる。
合同算術メソッドの一覧
通常の演算子 +, -, *, /1, ** もあり 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 は適当な数2（※満たすべき条件はある）
- 秘密鍵 (n, d) は鍵ペアの作成者しか知らない
- n は公開鍵と同じ3
- 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)