スカラー倍算
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/04/14 16:12 UTC 版)
スカラー倍算(Scalar Multiplication)は楕円曲線上における掛け算である。楕円曲線上の点と点を掛けるのではなく、点に整数(スカラー)を掛けることに注意。 暗号化・復号の過程において、 Q = d P {\displaystyle Q=dP} ( P , Q {\displaystyle P,\,Q} は楕円曲線上の点)という演算を行う。ナイーヴな実装としては Q = ( ⋯ ( ( P + P ) + P ) + ⋯ ) + P {\displaystyle Q=(\cdots ((P+P)+P)+\cdots )+P} というように Pを ( d − 1 ) {\displaystyle (d-1)} 回加算(1回目は2倍算となる)するが、これでは効率が悪い。 スカラー倍算はRSA暗号などにおけるべき乗剰余演算とリンクしており、これの高速化手法もそれから流用できるものが多い。例えば、そのひとつとして有名なBinary法では、dを2進数表記し、dの各ビット d i {\displaystyle d_{i}} が "0" の場合は2倍算のみを行い、"1" の場合は2倍算と加算を行うことにより、ナイーブな実装と同じ計算をより高速に行なっている。この計算手法では、2倍算はべき乗剰余演算における自乗算、加算は掛け算にそれぞれ対応している。 この演算は楕円曲線暗号の根幹を成している部分であり、楕円曲線暗号を利用する際の時間の大半を占めている。ゆえに、ICカードなどハードウェア上に演算回路を実装する場合はサイドチャネル攻撃(特にSPA、DPA)のターゲットとなる箇所なので工夫が必要となる。
※この「スカラー倍算」の解説は、「楕円曲線暗号」の解説の一部です。
「スカラー倍算」を含む「楕円曲線暗号」の記事については、「楕円曲線暗号」の概要を参照ください。
- スカラー倍算のページへのリンク