第 3 章 既存研究 9
4.4 iPhone における実験
4.4.3 スカラー倍算の高速化
以上の高速化手法を利用して，スカラー倍算の高速化を行なう．結果として，従来の方 法に対して63.09%の時間でスカラー倍算が実行された．
表 4.33: スカラー倍算の処理速度(ARM C言語) 実行時間(単位:µs) 比率(%)
従来 31700 100.00
提案方法 20000 63.09
第 5 章 結論
本研究では，ARMプロセッサにおける楕円スカラー倍算の実装を行なった．スカラー 倍算の内部で呼び出す多倍長演算は，条件分岐を削減し，演算をマージすることによって 効率を改善することが可能である．特にARMプロセッサを実装する小型機器は，メモリ のデータ転送速度が遅い場合が多く，演算のマージによってメモリアクセスの回数を削 減することが，高速化を実現するために重要である．演算のマージを行なうにあたって，
ARMプロセッサの得意とするシフト演算と，複数ワードのデータをまとめて転送する命 令を利用し，従来の多倍長演算の実行時間を約80%削減することができた．結果として，
高速化した多倍長演算と最新の加法公式を利用し，楕円スカラー倍算の実行時間を従来の
約63%まで削減するという結果を得た．
謝辞
本研究を遂行するにあたり，宮地充子教授からは多大なるご指導とご助言を賜わりまし た．幾度と無く励ましのお言葉をいただき，社会人として働きながら研究を進めるという，
決して平坦ではない道のりをここまで歩むことができました．研究に対しては厳しく，人 としては優しく接してくださったおかげで，私は成長することができたのだと思います．
心より感謝申し上げます．また宮地研究室の諸氏には，石川と東京の距離をこえて，交友 を結んでくださいました．研究に関して質問があれば即座に返答していただき，参考とな る文献があれば送っていただきました．本研究の成果は，そのような協力なしにはありえ なかったことを，ここに記します．
参考文献
[1] Henri Cohen, Gerhard Fray, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren ‘HANDBOOK OF ELLIPTIC AND HYPERELLIPTIC CURVE CRYPTOGRAPHY’, 2006
[2] Marc Joye and Sung-Ming Yen ‘The Montgomery Powering Ladder, 2002
[3] Peter L. Montgomery. Speeding the Pollard and elliptic curve methods of factorization.
Mathematics of Computation, January 1987.
[4] Alfred Brauer, ‘On Addition Chains’, 1939
[5] Andrew D. Booth, ‘A SIGNED BINARY MULTIPLICATION TECHNIQUE’, 1950 [6] F. Morain & J. Olivios, ‘Speeding up the computations on an elliptic curve using
addition-subtraction chains’, 1990
[7] Bodo Moeller, ‘Algorithms for Multi-exponentiation’, 2001
[8] Daniel J. Bernstein and Tanja Lange, ‘Faster addition and doubling on elliptic curves’, 2007 [9] T. Yanik, E. Savas, and C. K. Koc ‘Incomplete Reduction in Modular Arithmetic’,
Com-puters and Digital Technique, 149(2):46-52, March 2002
[10] Patrick Longa, and Catherine Gebotys ‘Efficient Techniques for High-Speed Elliptic Curve Cryptography’, 2010
[11] Patrick Longa, and Catherine Gebotys ‘Analysis of Efficient Techniques for Fast Elliptic Curve Cryptography on x86-64 based Processors’, 2010
[12] David Seal ‘ARM Architecture Reference Manual Second Edition’, 2000 [13] ARMプレスルーム, http://www.jp.arm.com/pressroom/08/080125.html, 2008 [14] OpenSSL Project, http://www.openssl.org/, 2010.
付 録 A 実験で使用したソースコード
OpenSSLライブラリ[14]より，C及びx86アセンブリ言語で記述されたプログラムを引用した．
引用したプログラムのキャプションには，引用番号[14]がふられている．一方で我々が提案する 方法は，x86アセンブリ言語で記述されたプログラムの中で，条件分岐を削減したものと，ARM アセンブリ言語で記述されたプログラムである．
■bn mul normal(): r =a×bを求める
・input:
BN ULONG *r: 計算結果を格納する開始アドレス
BN ULONG *a: 多倍長変数aのアドレス
int na: 多倍長変数aのワード数
BN ULONG *b: 多倍長変数bのアドレス
int nb: 多倍長変数bのワード数
・output:
戻り値なし．
ソースコードA.1: bn mul normal[14]
1 void bn m ul normal (BN ULONG ∗r , BN ULONG ∗a , i n t na ,
2 BN ULONG ∗b , i n t nb )
3 {
4 BN ULONG ∗r r ;
5
6 #i f d e f BN COUNT
7 f p r i n t f ( s t d e r r , ” bn m ul normal %d ∗ %d\n” , na , nb ) ;
8 #endif
9
10 i f ( na < nb )
11 {
12 i n t itmp ;
13 BN ULONG ∗ltmp ;
14
15 itmp=na ; na=nb ; nb=itmp ;
16 ltmp=a ; a=b ; b=ltmp ;
17
18 }
19 r r= &( r [ na ] ) ;
20 i f ( nb <= 0 )
21 {
22 (void) bn mul words ( r , a , na , 0 ) ;
23 return;
24 }
25 e l s e
26 r r [ 0 ] = bn mul words ( r , a , na , b [ 0 ] ) ;
27
28 f o r ( ; ; )
29 {
30 i f (−−nb <= 0 ) return;
31 r r [ 1 ] = b n m u l a d d w o r d s (&( r [ 1 ] ) , a , na , b [ 1 ] ) ;
32 i f (−−nb <= 0 ) return;
33 r r [ 2 ] = b n m u l a d d w o r d s (&( r [ 2 ] ) , a , na , b [ 2 ] ) ;
34 i f (−−nb <= 0 ) return;
35 r r [ 3 ] = b n m u l a d d w o r d s (&( r [ 3 ] ) , a , na , b [ 3 ] ) ;
36 i f (−−nb <= 0 ) return;
37 r r [ 4 ] = b n m u l a d d w o r d s (&( r [ 4 ] ) , a , na , b [ 4 ] ) ;
38 r r +=4;
39 r +=4;
40 b+=4;
41 }
42 }
■bn sqr normal(): r=a×aを求める
・input:
BN ULONG *r: 計算結果を格納する開始アドレス
BN ULONG *a: 多倍長変数aのアドレス
int n: 多倍長変数aのワード数
BN ULONG *tmp: 計算用領域のアドレス
・output:
戻り値なし．
ソースコードA.2: bn sqr normal[14]
1 void b n s q r n o r m a l (BN ULONG ∗r , const BN ULONG ∗a ,
2 i n t n , BN ULONG ∗tmp )
3 {
4 i n t i , j , max ;
5 const BN ULONG ∗ap ;
6 BN ULONG ∗rp ;
7
8 max=n∗2 ;
9 ap=a ;
10 rp=r ;
11 rp [ 0 ] = rp [ max−1]=0;
12 rp++;
13 j=n ;
15 i f (−−j > 0 )
16 {
17 ap++;
18 rp [ j ]= bn mul words ( rp , ap , j , ap [−1 ] ) ;
19 rp +=2;
20 }
21
22 f o r ( i=n−2; i>0; i−−)
23 {
24 j−−;
25 ap++;
26 rp [ j ]= b n m u l a d d w o r d s ( rp , ap , j , ap [−1 ] ) ;
27 rp +=2;
28 }
29
30 b n a d d w o r d s ( r , r , r , max ) ;
31
32 /∗ There w i l l n o t b e a c a r r y ∗/
33
34 b n s q r w o r d s ( tmp , a , n ) ;
35
36 b n a d d w o r d s ( r , r , tmp , max ) ;
37 }
■bn mul words(): rp=ap×wを求める
・input:
BN ULONG *rp: 計算結果を格納する開始アドレス
BN ULONG *ap: 多倍長変数apのアドレス int num: 多倍長変数apのワード数
BN ULONG w: ワード長変数
・output:
戻り値 BN ULONG:乗算の繰り上がり値
ソースコード A.3: bn mul words[14]
1 . t e x t
2 . g l o b l b n m u l w o r d s
3 b n m u l w o r d s :
4 p u s h l %ebp
5 p u s h l %ebx
6 p u s h l %e s i
7 p u s h l %e d i
8 9
10 x o r l %e s i , %e s i
11 movl 20(% e s p ) , %e d i
12 movl 24(% e s p ) , %ebx
13 movl 28(% e s p ) , %ebp
14 movl 32(% e s p ) , %e c x
15 a n d l $4294967288 , %ebp
16 j z . L 0 0 4 m w f i n i s h
17 . L005mw loop :
18
19 movl (%ebx ) , %eax
20 m u l l %e c x
21 a d d l %e s i , %eax
22 a d c l $0 , %edx
23 movl %eax , (% e d i )
24 movl %edx , %e s i
25
26 movl 4(%ebx ) , %eax
27 m u l l %e c x
28 a d d l %e s i , %eax
29 a d c l $0 , %edx
30 movl %eax , 4(% e d i )
31 movl %edx , %e s i
32
33 movl 8(%ebx ) , %eax
34 m u l l %e c x
35 a d d l %e s i , %eax
36 a d c l $0 , %edx
37 movl %eax , 8(% e d i )
38 movl %edx , %e s i
39
40 movl 12(% ebx ) , %eax
41 m u l l %e c x
42 a d d l %e s i , %eax
43 a d c l $0 , %edx
44 movl %eax , 12(% e d i )
45 movl %edx , %e s i
46
47 movl 16(% ebx ) , %eax
48 m u l l %e c x
49 a d d l %e s i , %eax
50 a d c l $0 , %edx
51 movl %eax , 16(% e d i )
52 movl %edx , %e s i
53
54 movl 20(% ebx ) , %eax
55 m u l l %e c x
56 a d d l %e s i , %eax
57 a d c l $0 , %edx
58 movl %eax , 20(% e d i )
59 movl %edx , %e s i
60
61 movl 24(% ebx ) , %eax
62 m u l l %e c x
63 a d d l %e s i , %eax
64 a d c l $0 , %edx
65 movl %eax , 24(% e d i )
66 movl %edx , %e s i
67
68 movl 28(% ebx ) , %eax
69 m u l l %e c x
70 a d d l %e s i , %eax
71 a d c l $0 , %edx
72 movl %eax , 28(% e d i )
73 movl %edx , %e s i
74
75 a d d l $32 , %ebx
76 a d d l $32 , %e d i
77 s u b l $8 , %ebp
78 j z . L 0 0 4 m w f i n i s h
79 jmp . L005mw loop
80 . L 0 0 4 m w f i n i s h :
81 movl 28(% e s p ) , %ebp
82 a n d l $7 , %ebp
83 j n z . L 0 0 6 m w f i n i s h 2
84 jmp . L007mw end
85 . L 0 0 6 m w f i n i s h 2 :
86
87 movl (%ebx ) , %eax
88 m u l l %e c x
89 a d d l %e s i , %eax
90 a d c l $0 , %edx
91 movl %eax , (% e d i )
92 movl %edx , %e s i
93 d e c l %ebp
94 j z . L007mw end
95
96 movl 4(%ebx ) , %eax
97 m u l l %e c x
98 a d d l %e s i , %eax
99 a d c l $0 , %edx
100 movl %eax , 4(% e d i )
101 movl %edx , %e s i
102 d e c l %ebp
103 j z . L007mw end
104
105 movl 8(%ebx ) , %eax
106 m u l l %e c x
107 a d d l %e s i , %eax
108 a d c l $0 , %edx
109 movl %eax , 8(% e d i )
110 movl %edx , %e s i
111 d e c l %ebp
112 j z . L007mw end
113
114 movl 12(% ebx ) , %eax
115 m u l l %e c x
116 a d d l %e s i , %eax
117 a d c l $0 , %edx
118 movl %eax , 12(% e d i )
119 movl %edx , %e s i
120 d e c l %ebp
121 j z . L007mw end
122
123 movl 16(% ebx ) , %eax
124 m u l l %e c x
125 a d d l %e s i , %eax
126 a d c l $0 , %edx
127 movl %eax , 16(% e d i )
128 movl %edx , %e s i
129 d e c l %ebp
130 j z . L007mw end
131
132 movl 20(% ebx ) , %eax
133 m u l l %e c x
134 a d d l %e s i , %eax
135 a d c l $0 , %edx
136 movl %eax , 20(% e d i )
137 movl %edx , %e s i
138 d e c l %ebp
139 j z . L007mw end
140
141 movl 24(% ebx ) , %eax
142 m u l l %e c x
143 a d d l %e s i , %eax
144 a d c l $0 , %edx
145 movl %eax , 24(% e d i )
146 movl %edx , %e s i
147 . L007mw end :
148 movl %e s i , %eax
149 p o p l %e d i
150 p o p l %e s i
151 p o p l %ebx
152 p o p l %ebp
153 r e t
154 . L b n m u l w o r d s e n d :
■bn mul add words(): 積和rp=rp+ap×wを求める
・input:
BN ULONG *rp: 計算結果を格納する開始アドレス
BN ULONG *ap: 多倍長変数apのアドレス int num: 多倍長変数apのワード数
BN ULONG w: ワード長変数
・output:
戻り値 BN ULONG:乗算の繰り上がり値
ソースコードA.4: bn mul add words[14]
1 . t e x t
2 . g l o b l b n m u l a d d w o r d s
3 b n m u l a d d w o r d s :
4 p u s h l %ebp
5 p u s h l %ebx
6 p u s h l %e s i
7 p u s h l %e d i
8 9
10 x o r l %e s i , %e s i
11 movl 20(% e s p ) , %e d i
12 movl 28(% e s p ) , %e c x
13 movl 24(% e s p ) , %ebx
14 a n d l $4294967288 , %e c x
15 movl 32(% e s p ) , %ebp
16 p u s h l %e c x
17 j z . L 0 0 0 m a w f i n i s h
18 . L001maw loop :
19 movl %ecx , (% e s p )
20
21 movl (%ebx ) , %eax
22 m u l l %ebp
23 a d d l %e s i , %eax
24 movl (% e d i ) , %e s i
25 a d c l $0 , %edx
26 a d d l %e s i , %eax
27 a d c l $0 , %edx
28 movl %eax , (% e d i )
29 movl %edx , %e s i
30
31 movl 4(%ebx ) , %eax
32 m u l l %ebp
33 a d d l %e s i , %eax
34 movl 4(% e d i ) , %e s i
35 a d c l $0 , %edx
36 a d d l %e s i , %eax
37 a d c l $0 , %edx
38 movl %eax , 4(% e d i )
39 movl %edx , %e s i
40
41 movl 8(%ebx ) , %eax
42 m u l l %ebp
43 a d d l %e s i , %eax
44 movl 8(% e d i ) , %e s i
45 a d c l $0 , %edx
46 a d d l %e s i , %eax
47 a d c l $0 , %edx
48 movl %eax , 8(% e d i )
49 movl %edx , %e s i
50
51 movl 12(% ebx ) , %eax
52 m u l l %ebp
53 a d d l %e s i , %eax
54 movl 12(% e d i ) , %e s i
55 a d c l $0 , %edx
56 a d d l %e s i , %eax
57 a d c l $0 , %edx
58 movl %eax , 12(% e d i )
59 movl %edx , %e s i
60
61 movl 16(% ebx ) , %eax
62 m u l l %ebp
63 a d d l %e s i , %eax
64 movl 16(% e d i ) , %e s i
65 a d c l $0 , %edx
66 a d d l %e s i , %eax
67 a d c l $0 , %edx
68 movl %eax , 16(% e d i )
69 movl %edx , %e s i
70
71 movl 20(% ebx ) , %eax
72 m u l l %ebp
73 a d d l %e s i , %eax
74 movl 20(% e d i ) , %e s i
75 a d c l $0 , %edx
76 a d d l %e s i , %eax
77 a d c l $0 , %edx
78 movl %eax , 20(% e d i )
79 movl %edx , %e s i
80
81 movl 24(% ebx ) , %eax
82 m u l l %ebp
83 a d d l %e s i , %eax
84 movl 24(% e d i ) , %e s i
85 a d c l $0 , %edx
86 a d d l %e s i , %eax
87 a d c l $0 , %edx
88 movl %eax , 24(% e d i )
89 movl %edx , %e s i
90
91 movl 28(% ebx ) , %eax
92 m u l l %ebp
93 a d d l %e s i , %eax
94 movl 28(% e d i ) , %e s i
95 a d c l $0 , %edx
96 a d d l %e s i , %eax
97 a d c l $0 , %edx
98 movl %eax , 28(% e d i )
99 movl %edx , %e s i
100
101 movl (% e s p ) , %e c x
102 a d d l $32 , %ebx
103 a d d l $32 , %e d i
104 s u b l $8 , %e c x
105 j n z . L001maw loop
106 . L 0 0 0 m a w f i n i s h :
107 movl 32(% e s p ) , %e c x
108 a n d l $7 , %e c x
109 j n z . L 0 0 2 m a w f i n i s h 2
110 jmp . L003maw end
111 . L 0 0 2 m a w f i n i s h 2 :
112
113 movl (%ebx ) , %eax
114 m u l l %ebp
115 a d d l %e s i , %eax
116 movl (% e d i ) , %e s i
117 a d c l $0 , %edx
118 a d d l %e s i , %eax
119 a d c l $0 , %edx
120 d e c l %e c x
121 movl %eax , (% e d i )
122 movl %edx , %e s i
123 j z . L003maw end
124
125 movl 4(%ebx ) , %eax
126 m u l l %ebp
127 a d d l %e s i , %eax
128 movl 4(% e d i ) , %e s i
129 a d c l $0 , %edx
130 a d d l %e s i , %eax
131 a d c l $0 , %edx
132 d e c l %e c x
133 movl %eax , 4(% e d i )
134 movl %edx , %e s i
135 j z . L003maw end
136
137 movl 8(%ebx ) , %eax
138 m u l l %ebp
139 a d d l %e s i , %eax
140 movl 8(% e d i ) , %e s i
141 a d c l $0 , %edx
142 a d d l %e s i , %eax
143 a d c l $0 , %edx
144 d e c l %e c x
145 movl %eax , 8(% e d i )
146 movl %edx , %e s i
147 j z . L003maw end
148
149 movl 12(% ebx ) , %eax
150 m u l l %ebp
151 a d d l %e s i , %eax
152 movl 12(% e d i ) , %e s i
153 a d c l $0 , %edx
154 a d d l %e s i , %eax
155 a d c l $0 , %edx
156 d e c l %e c x
157 movl %eax , 12(% e d i )
158 movl %edx , %e s i
159 j z . L003maw end
160
161 movl 16(% ebx ) , %eax
162 m u l l %ebp
163 a d d l %e s i , %eax
164 movl 16(% e d i ) , %e s i
165 a d c l $0 , %edx
166 a d d l %e s i , %eax
167 a d c l $0 , %edx
168 d e c l %e c x
169 movl %eax , 16(% e d i )
170 movl %edx , %e s i
171 j z . L003maw end
172
173 movl 20(% ebx ) , %eax
174 m u l l %ebp
175 a d d l %e s i , %eax
176 movl 20(% e d i ) , %e s i
177 a d c l $0 , %edx
178 a d d l %e s i , %eax
179 a d c l $0 , %edx
180 d e c l %e c x
181 movl %eax , 20(% e d i )
182 movl %edx , %e s i
183 j z . L003maw end
184
185 movl 24(% ebx ) , %eax
186 m u l l %ebp
187 a d d l %e s i , %eax
188 movl 24(% e d i ) , %e s i
189 a d c l $0 , %edx
190 a d d l %e s i , %eax
191 a d c l $0 , %edx
192 movl %eax , 24(% e d i )
193 movl %edx , %e s i
194 . L003maw end :
195 movl %e s i , %eax
196 p o p l %e c x
197 p o p l %e d i
198 p o p l %e s i
199 p o p l %ebx
200 p o p l %ebp
201 r e t
202 . L b n m u l a d d w o r d s e n d :
■bn sqr words(): 各ワードの２乗を求める
・input:
BN ULONG *r: 計算結果を格納する開始アドレス
BN ULONG *a: 多倍長変数aのアドレス
int n: 多倍長変数aのワード数
・output:
戻り値 なし
ソースコード A.5: bn sqr words[14]
1 . t e x t
2 . g l o b l b n s q r w o r d s
3 b n s q r w o r d s :
4 p u s h l %ebp
5 p u s h l %ebx
6 p u s h l %e s i
7 p u s h l %e d i
8 9
10 movl 20(% e s p ) , %e s i
11 movl 24(% e s p ) , %e d i
12 movl 28(% e s p ) , %ebx
13 a n d l $4294967288 , %ebx
14 j z . L 0 0 8 s w f i n i s h
15 . L 0 0 9 s w l o o p :
16
17 movl (% e d i ) , %eax
18 m u l l %eax
19 movl %eax , (% e s i )
20 movl %edx , 4(% e s i )
21
22 movl 4(% e d i ) , %eax
23 m u l l %eax
24 movl %eax , 8(% e s i )
25 movl %edx , 12(% e s i )
26
27 movl 8(% e d i ) , %eax
28 m u l l %eax
29 movl %eax , 16(% e s i )
30 movl %edx , 20(% e s i )
31
32 movl 12(% e d i ) , %eax
33 m u l l %eax
34 movl %eax , 24(% e s i )
35 movl %edx , 28(% e s i )
36
37 movl 16(% e d i ) , %eax
38 m u l l %eax
39 movl %eax , 32(% e s i )
40 movl %edx , 36(% e s i )
41
42 movl 20(% e d i ) , %eax
43 m u l l %eax
44 movl %eax , 40(% e s i )
45 movl %edx , 44(% e s i )
46
47 movl 24(% e d i ) , %eax
48 m u l l %eax
49 movl %eax , 48(% e s i )
50 movl %edx , 52(% e s i )
51
52 movl 28(% e d i ) , %eax
53 m u l l %eax
54 movl %eax , 56(% e s i )
55 movl %edx , 60(% e s i )
56
57 a d d l $32 , %e d i
58 a d d l $64 , %e s i
59 s u b l $8 , %ebx
60 j n z . L 0 0 9 s w l o o p
61 . L 0 0 8 s w f i n i s h :
62 movl 28(% e s p ) , %ebx
63 a n d l $7 , %ebx
64 j z . L010sw end
65
66 movl (% e d i ) , %eax
67 m u l l %eax
68 movl %eax , (% e s i )
69 d e c l %ebx
70 movl %edx , 4(% e s i )
71 j z . L010sw end
72
73 movl 4(% e d i ) , %eax
74 m u l l %eax
75 movl %eax , 8(% e s i )
76 d e c l %ebx
77 movl %edx , 12(% e s i )
78 j z . L010sw end
79
80 movl 8(% e d i ) , %eax
81 m u l l %eax
82 movl %eax , 16(% e s i )
83 d e c l %ebx
84 movl %edx , 20(% e s i )
85 j z . L010sw end
86
87 movl 12(% e d i ) , %eax
88 m u l l %eax
89 movl %eax , 24(% e s i )
90 d e c l %ebx
91 movl %edx , 28(% e s i )
92 j z . L010sw end
93
94 movl 16(% e d i ) , %eax
95 m u l l %eax
96 movl %eax , 32(% e s i )
97 d e c l %ebx
98 movl %edx , 36(% e s i )
99 j z . L010sw end
100
101 movl 20(% e d i ) , %eax
102 m u l l %eax
103 movl %eax , 40(% e s i )
104 d e c l %ebx
105 movl %edx , 44(% e s i )
106 j z . L010sw end
107
108 movl 24(% e d i ) , %eax
109 m u l l %eax
110 movl %eax , 48(% e s i )
111 movl %edx , 52(% e s i )
112 . L010sw end :
113 p o p l %e d i
114 p o p l %e s i
115 p o p l %ebx
116 p o p l %ebp
117 r e t
118 . L b n s q r w o r d s e n d :
■bn add words(): r =a+bを求める
・input:
BN ULONG *r: 計算結果を格納する開始アドレス
BN ULONG *a: 多倍長変数aのアドレス
BN ULONG *b: 多倍長変数bのアドレス
int n: 多倍長変数aまたはbの大きな方のワード数
・output:
戻り値 BN ULONG:繰り上がり値
ソースコードA.6: bn add words[14]
1 . t e x t
2 . g l o b l b n a d d w o r d s
3 b n a d d w o r d s :
4 p u s h l %ebp
5 p u s h l %ebx
6 p u s h l %e s i
7 p u s h l %e d i
8
10 movl 20(% e s p ) , %ebx
11 movl 24(% e s p ) , %e s i
12 movl 28(% e s p ) , %e d i
13 movl 32(% e s p ) , %ebp
14 x o r l %eax , %eax
15 a n d l $4294967288 , %ebp
16 j z . L 0 1 1 a w f i n i s h
17 . L012aw loop :
18
19 movl (% e s i ) , %e c x
20 movl (% e d i ) , %edx
21 a d d l %eax , %e c x
22 movl $0 , %eax
23 a d c l %eax , %eax
24 a d d l %edx , %e c x
25 a d c l $0 , %eax
26 movl %ecx , (%ebx )
27
28 movl 4(% e s i ) , %e c x
29 movl 4(% e d i ) , %edx
30 a d d l %eax , %e c x
31 movl $0 , %eax
32 a d c l %eax , %eax
33 a d d l %edx , %e c x
34 a d c l $0 , %eax
35 movl %ecx , 4(%ebx )
36
37 movl 8(% e s i ) , %e c x
38 movl 8(% e d i ) , %edx
39 a d d l %eax , %e c x
40 movl $0 , %eax
41 a d c l %eax , %eax
42 a d d l %edx , %e c x
43 a d c l $0 , %eax
44 movl %ecx , 8(%ebx )
45
46 movl 12(% e s i ) , %e c x
47 movl 12(% e d i ) , %edx
48 a d d l %eax , %e c x
49 movl $0 , %eax
50 a d c l %eax , %eax
51 a d d l %edx , %e c x
52 a d c l $0 , %eax
53 movl %ecx , 12(% ebx )
54
55 movl 16(% e s i ) , %e c x
56 movl 16(% e d i ) , %edx
57 a d d l %eax , %e c x
58 movl $0 , %eax
59 a d c l %eax , %eax
60 a d d l %edx , %e c x
61 a d c l $0 , %eax
62 movl %ecx , 16(% ebx )
63
64 movl 20(% e s i ) , %e c x
65 movl 20(% e d i ) , %edx
66 a d d l %eax , %e c x
67 movl $0 , %eax
68 a d c l %eax , %eax
69 a d d l %edx , %e c x
70 a d c l $0 , %eax
71 movl %ecx , 20(% ebx )
72
73 movl 24(% e s i ) , %e c x
74 movl 24(% e d i ) , %edx
75 a d d l %eax , %e c x
76 movl $0 , %eax
77 a d c l %eax , %eax
78 a d d l %edx , %e c x
79 a d c l $0 , %eax
80 movl %ecx , 24(% ebx )
81
82 movl 28(% e s i ) , %e c x
83 movl 28(% e d i ) , %edx
84 a d d l %eax , %e c x
85 movl $0 , %eax
86 a d c l %eax , %eax
87 a d d l %edx , %e c x
88 a d c l $0 , %eax
89 movl %ecx , 28(% ebx )
90
91 a d d l $32 , %e s i
92 a d d l $32 , %e d i
93 a d d l $32 , %ebx
94 s u b l $8 , %ebp
95 j n z . L012aw loop
96 . L 0 1 1 a w f i n i s h :
97 movl 32(% e s p ) , %ebp
98 a n d l $7 , %ebp
99 j z . L013aw end
100
101 movl (% e s i ) , %e c x
102 movl (% e d i ) , %edx
103 a d d l %eax , %e c x
104 movl $0 , %eax
105 a d c l %eax , %eax
106 a d d l %edx , %e c x
107 a d c l $0 , %eax
108 d e c l %ebp
109 movl %ecx , (%ebx )
110 j z . L013aw end
111
112 movl 4(% e s i ) , %e c x
113 movl 4(% e d i ) , %edx
114 a d d l %eax , %e c x
115 movl $0 , %eax
116 a d c l %eax , %eax
117 a d d l %edx , %e c x
118 a d c l $0 , %eax
119 d e c l %ebp
120 movl %ecx , 4(%ebx )
121 j z . L013aw end
122
123 movl 8(% e s i ) , %e c x
124 movl 8(% e d i ) , %edx
125 a d d l %eax , %e c x
126 movl $0 , %eax
127 a d c l %eax , %eax
128 a d d l %edx , %e c x
129 a d c l $0 , %eax
130 d e c l %ebp
131 movl %ecx , 8(%ebx )
132 j z . L013aw end
133
134 movl 12(% e s i ) , %e c x
135 movl 12(% e d i ) , %edx
136 a d d l %eax , %e c x
137 movl $0 , %eax
138 a d c l %eax , %eax
139 a d d l %edx , %e c x
140 a d c l $0 , %eax
141 d e c l %ebp
142 movl %ecx , 12(% ebx )
143 j z . L013aw end
144
145 movl 16(% e s i ) , %e c x
146 movl 16(% e d i ) , %edx
147 a d d l %eax , %e c x
148 movl $0 , %eax
149 a d c l %eax , %eax
150 a d d l %edx , %e c x
151 a d c l $0 , %eax
152 d e c l %ebp
153 movl %ecx , 16(% ebx )
154 j z . L013aw end
155
156 movl 20(% e s i ) , %e c x
157 movl 20(% e d i ) , %edx
158 a d d l %eax , %e c x
159 movl $0 , %eax
160 a d c l %eax , %eax
161 a d d l %edx , %e c x
162 a d c l $0 , %eax
163 d e c l %ebp
164 movl %ecx , 20(% ebx )
165 j z . L013aw end
166
167 movl 24(% e s i ) , %e c x
168 movl 24(% e d i ) , %edx
169 a d d l %eax , %e c x
170 movl $0 , %eax
171 a d c l %eax , %eax
172 a d d l %edx , %e c x
173 a d c l $0 , %eax
174 movl %ecx , 24(% ebx )
175 . L013aw end :
176 p o p l %e d i
177 p o p l %e s i
178 p o p l %ebx
179 p o p l %ebp
180 r e t
181 . L b n a d d w o r d s e n d :
■bn add 10 words(): 10 wordsの値r=a+bを求める
・input:
BN ULONG *r: 計算結果を格納する開始アドレス
BN ULONG *a: 多倍長変数aのアドレス
BN ULONG *b: 多倍長変数bのアドレス
・output:
戻り値 なし
ソースコード A.7: bn add 10 words
1 . t e x t
3 b n a d d 1 0 w o r d s :
4 p u s h l %ebp
5 p u s h l %ebx
6 p u s h l %e s i
7 p u s h l %e d i
8
9 movl 20(% e s p ) , %ebx
10 movl 24(% e s p ) , %e s i
11 movl 28(% e s p ) , %e d i
12 c l c
13
14 movl (% e s i ) , %e c x
15 movl (% e d i ) , %edx
16 a d d l %edx , %e c x
17 movl %ecx , (%ebx )
18
19 movl 4(% e s i ) , %e c x
20 movl 4(% e d i ) , %edx
21 a d c l %edx , %e c x
22 movl %ecx , 4(%ebx )
23
24 movl 8(% e s i ) , %e c x
25 movl 8(% e d i ) , %edx
26 a d c l %edx , %e c x
27 movl %ecx , 8(%ebx )
28
29 movl 12(% e s i ) , %e c x
30 movl 12(% e d i ) , %edx
31 a d c l %edx , %e c x
32 movl %ecx , 12(% ebx )
33
34 movl 16(% e s i ) , %e c x
35 movl 16(% e d i ) , %edx
36 a d c l %edx , %e c x
37 movl %ecx , 16(% ebx )
38
39 movl 20(% e s i ) , %e c x
40 movl 20(% e d i ) , %edx
41 a d c l %edx , %e c x
42 movl %ecx , 20(% ebx )
43
44 movl 24(% e s i ) , %e c x
45 movl 24(% e d i ) , %edx
46 a d c l %edx , %e c x
47 movl %ecx , 24(% ebx )
48
49 movl 28(% e s i ) , %e c x
50 movl 28(% e d i ) , %edx
51 a d c l %edx , %e c x
52 movl %ecx , 28(% ebx )
53
54 movl 32(% e s i ) , %e c x
55 movl 32(% e d i ) , %edx
56 a d c l %edx , %e c x
57 movl %ecx , 32(% ebx )
58
59 movl 36(% e s i ) , %e c x
60 movl 36(% e d i ) , %edx
61 a d c l %edx , %e c x
62 movl %ecx , 36(% ebx )
63
64 p o p l %e d i
65 p o p l %e s i
66 p o p l %ebx
67 p o p l %ebp
68 r e t
69 . L b n a d d 1 0 w o r d s e n d :
■bn mul 4 words(): rp=ap×wを求める
・input:
BN ULONG *rp: 計算結果を格納する開始アドレス
BN ULONG *ap: 多倍長変数apのアドレス
BN ULONG w: ワード長変数
・output:
戻り値 BN ULONG:乗算の繰り上がり値
ソースコードA.8: bn mul 4 words
1 . t e x t
2 . g l o b l b n m u l 4 w o r d s
3 b n m u l 4 w o r d s :
4 p u s h l %ebp
5 p u s h l %ebx
6 p u s h l %e s i
7 p u s h l %e d i
8
9 x o r l %e s i , %e s i
10 movl 20(% e s p ) , %e d i
11 movl 24(% e s p ) , %ebx
12 movl 28(% e s p ) , %e c x
13
15 m u l l %e c x
16 movl %eax , (% e d i )
17 movl %edx , %e s i
18
19 movl 4(%ebx ) , %eax
20 m u l l %e c x
21 a d d l %e s i , %eax
22 a d c l $0 , %edx
23 movl %eax , 4(% e d i )
24 movl %edx , %e s i
25
26 movl 8(%ebx ) , %eax
27 m u l l %e c x
28 a d d l %e s i , %eax
29 a d c l $0 , %edx
30 movl %eax , 8(% e d i )
31 movl %edx , %e s i
32
33 movl 12(% ebx ) , %eax
34 m u l l %e c x
35 a d d l %e s i , %eax
36 a d c l $0 , %edx
37 movl %eax , 12(% e d i )
38 movl %edx , %e s i
39
40 movl %e s i , %eax
41
42 p o p l %e d i
43 p o p l %e s i
44 p o p l %ebx
45 p o p l %ebp
46 r e t
47 . L b n m u l 4 w o r d s e n d :
■bn mul add 3 words(): 積和rp=rp+ap×wを求める
・input:
BN ULONG *rp: 計算結果を格納する開始アドレス
BN ULONG *ap: 多倍長変数apのアドレス
BN ULONG w: ワード長変数
・output:
戻り値 BN ULONG:乗算の繰り上がり値
ソースコード A.9: bn mul add 3 words
1 . t e x t
2 . g l o b l b n m u l a d d 3 w o r d s
3 b n m u l a d d 3 w o r d s :
4 p u s h l %ebp
5 p u s h l %ebx
6 p u s h l %e s i
7 p u s h l %e d i
8
9 x o r l %e s i , %e s i
10 movl 20(% e s p ) , %e d i
11 movl 24(% e s p ) , %ebx
12 movl 28(% e s p ) , %ebp
13
14 movl (%ebx ) , %eax
15 m u l l %ebp
16 a d d l %e s i , %eax
17 movl (% e d i ) , %e s i
18 a d c l $0 , %edx
19 a d d l %e s i , %eax
20 a d c l $0 , %edx
21 movl %eax , (% e d i )
22 movl %edx , %e s i
23
24 movl 4(%ebx ) , %eax
25 m u l l %ebp
26 a d d l %e s i , %eax
27 movl 4(% e d i ) , %e s i
28 a d c l $0 , %edx
29 a d d l %e s i , %eax
30 a d c l $0 , %edx
31 movl %eax , 4(% e d i )
32 movl %edx , %e s i
33
34 movl 8(%ebx ) , %eax
35 m u l l %ebp
36 a d d l %e s i , %eax
37 movl 8(% e d i ) , %e s i
38 a d c l $0 , %edx
39 a d d l %e s i , %eax
40 a d c l $0 , %edx
41 movl %eax , 8(% e d i )
42 movl %edx , %e s i
43
44 movl %e s i , %eax
45
46 p o p l %e d i
47 p o p l %e s i
48 p o p l %ebx
49 p o p l %ebp
50 r e t
51 . L b n m u l a d d 3 w o r d s e n d :
■bn mul add 2 words(): 積和rp=rp+ap×wを求める
・input:
BN ULONG *rp: 計算結果を格納する開始アドレス
BN ULONG *ap: 多倍長変数apのアドレス
BN ULONG w: ワード長変数
・output:
戻り値 BN ULONG:乗算の繰り上がり値
ソースコードA.10: bn mul add 2 words
1 . t e x t
2 . g l o b l b n m u l a d d 2 w o r d s
3 b n m u l a d d 2 w o r d s :
4 p u s h l %ebp
5 p u s h l %ebx
6 p u s h l %e s i
7 p u s h l %e d i
8
9 x o r l %e s i , %e s i
10 movl 20(% e s p ) , %e d i
11 movl 24(% e s p ) , %ebx
12 movl 28(% e s p ) , %ebp
13
14 movl (%ebx ) , %eax
15 m u l l %ebp
16 a d d l %e s i , %eax
17 movl (% e d i ) , %e s i
18 a d c l $0 , %edx
19 a d d l %e s i , %eax
20 a d c l $0 , %edx
21 movl %eax , (% e d i )
22 movl %edx , %e s i
23
24 movl 4(%ebx ) , %eax
25 m u l l %ebp
26 a d d l %e s i , %eax
27 movl 4(% e d i ) , %e s i
28 a d c l $0 , %edx
29 a d d l %e s i , %eax
30 a d c l $0 , %edx
31 movl %eax , 4(% e d i )
32 movl %edx , %e s i
33
34 movl %e s i , %eax
35
36 p o p l %e d i
37 p o p l %e s i
38 p o p l %ebx
39 p o p l %ebp
40 r e t
41 . L b n m u l a d d 2 w o r d s e n d :
■bn mul add 1 word(): 積和rp=rp+ap×wを求める
・input:
BN ULONG *rp: 計算結果を格納する開始アドレス
BN ULONG *ap: 多倍長変数apのアドレス
BN ULONG w: ワード長変数
・output:
戻り値 BN ULONG:乗算の繰り上がり値
ソースコード A.11: bn mul add 1 word
1 . t e x t
2 . g l o b l b n m u l a d d 1 w o r d
3 b n m u l a d d 1 w o r d :
4 p u s h l %ebp
5 p u s h l %ebx
6 p u s h l %e s i
7 p u s h l %e d i
8
9 x o r l %e s i , %e s i
10 movl 20(% e s p ) , %e d i
11 movl 24(% e s p ) , %ebx
12 movl 28(% e s p ) , %ebp
13
14 movl (%ebx ) , %eax
15 m u l l %ebp
16 movl (% e d i ) , %e s i
17 a d d l %e s i , %eax
18 a d c l $0 , %edx
19 movl %eax , (% e d i )
20 movl %edx , %e s i
21
22 movl %e s i , %eax
23
24 p o p l %e d i
25 p o p l %e s i
26 p o p l %ebx
28 r e t
29 . L b n m u l a d d 1 w o r d e n d :
■bn sqr 5 words(): 各ワードの２乗を求める
・input:
BN ULONG *r: 計算結果を格納する開始アドレス
BN ULONG *a: 多倍長変数aのアドレス
・output:
戻り値 なし
ソースコードA.12: bn sqr 5 words
1 . t e x t
2 . g l o b l b n s q r 5 w o r d s
3 b n s q r 5 w o r d s :
4 p u s h l %ebp
5 p u s h l %ebx
6 p u s h l %e s i
7 p u s h l %e d i
8
9 movl 20(% e s p ) , %e s i
10 movl 24(% e s p ) , %e d i
11
12 movl (% e d i ) , %eax
13 m u l l %eax
14 movl %eax , (% e s i )
15 movl %edx , 4(% e s i )
16
17 movl 4(% e d i ) , %eax
18 m u l l %eax
19 movl %eax , 8(% e s i )
20 movl %edx , 12(% e s i )
21
22 movl 8(% e d i ) , %eax
23 m u l l %eax
24 movl %eax , 16(% e s i )
25 movl %edx , 20(% e s i )
26
27 movl 12(% e d i ) , %eax
28 m u l l %eax
29 movl %eax , 24(% e s i )
30 movl %edx , 28(% e s i )
31
32 movl 16(% e d i ) , %eax
33 m u l l %eax
34 movl %eax , 32(% e s i )
35 movl %edx , 36(% e s i )
36
37 p o p l %e d i
38 p o p l %e s i
39 p o p l %ebx
40 p o p l %ebp
41 r e t
42 . L b n s q r 5 w o r d s e n d :
■bn mul words(): rp=ap×wを求める
・input:
BN ULONG *rp: 計算結果を格納する開始アドレス
BN ULONG *ap: 多倍長変数apのアドレス int num: 多倍長変数apのワード数
BN ULONG w: ワード長変数
・output:
戻り値 BN ULONG:乗算の繰り上がり値
ソースコードA.13: bn mul words.arm
1 asm BN ULONG bn mul words (
2 r e g i s t e r BN ULONG ∗rp ,
3 r e g i s t e r const BN ULONG ∗ap ,
4 r e g i s t e r i n t num ,
5 r e g i s t e r BN ULONG w)
6 {
7 mov r7 , #0
8 adds r8 , r7 , #0
9
10 l d r r9 , =0 x f f f f f f f 8
11 ands r10 , r2 , r 9
12 beq L 0 0 4 m w f i n i s h
13
14 L005mw loop :
15
16 l d r r4 , [ r 1 ]
17 umull r5 , r6 , r4 , r 3
18 adds r5 , r5 , r 7
19 a d c s r6 , r6 , r 8
20 s t r r5 , [ r 0 ]
21 mov r7 , r 6
22
23 l d r r4 , [ r1 , #4]
24 umull r5 , r6 , r4 , r 3
25 adds r5 , r5 , r 7
26 a d c s r6 , r6 , r 8
28 mov r7 , r 6
29
30 l d r r4 , [ r1 , #8]
31 umull r5 , r6 , r4 , r 3
32 adds r5 , r5 , r 7
33 a d c s r6 , r6 , r 8
34 s t r r5 , [ r0 , #8]
35 mov r7 , r 6
36
37 l d r r4 , [ r1 , #12]
38 umull r5 , r6 , r4 , r 3
39 adds r5 , r5 , r 7
40 a d c s r6 , r6 , r 8
41 s t r r5 , [ r0 , #12]
42 mov r7 , r 6
43
44 l d r r4 , [ r1 , #20]
45 umull r5 , r6 , r4 , r 3
46 adds r5 , r5 , r 7
47 a d c s r6 , r6 , r 8
48 s t r r5 , [ r0 , #20]
49 mov r7 , r 6
50
51 l d r r4 , [ r1 , #24]
52 umull r5 , r6 , r4 , r 3
53 adds r5 , r5 , r 7
54 a d c s r6 , r6 , r 8
55 s t r r5 , [ r0 , #24]
56 mov r7 , r 6
57
58 l d r r4 , [ r1 , #28]
59 umull r5 , r6 , r4 , r 3
60 adds r5 , r5 , r 7
61 a d c s r6 , r6 , r 8
62 s t r r5 , [ r0 , #28]
63 mov r7 , r 6
64
65 add r0 , r0 , #32
66 add r1 , r1 , #32
67 sub r2 , r2 , #8
68
69 beq L 0 0 4 m w f i n i s h
70 b L005mw loop
71
72 L 0 0 4 m w f i n i s h :
73