非常に今さら感がありますが、ちょっとRSAの処理時間を測ってみました。
【実行環境】
・Lenovo ThinkPad Edge E520
・Intel(R) Celeron(R) CPU B800 @ 1.50GHz (2コア)
・DDR3 8GB
・KEIAN SSD 30GB
・Lubuntu 20.04.3
・Python 3.8.10
・実行スクリプト https://github.com/fukuda123/crypto/blob/main/20211106-rsa_time/rsa_time.py
・実行結果 https://github.com/fukuda123/crypto/blob/main/20211106-rsa_time/result.txt
この結果では、鍵長をNとした時、暗号化・署名検証はO(N^1.56)、復号・署名生成はO(N^2.55)ぐらいですね。
ざっくり、O(N^2)とO(N^3)よりは小さいはずだと予想していましたので、概ね予想通りで満足しました。