README.bytecode
1MISHMASH bytecode
2=================
3
4bytecode = array of byte (implemented as uint8_t)
5
6Used to encode different way to perform scalar multiplication for ECM or fast
7exponentitation for p+1.
8This document described the MISHMASH bytecode in the context of ECM, but it can
9easily be translated for P+1.
10
11The MISHMASH bytecode encodes different blocks, each type of block can have its
12own encoding
13
14
15# Environment
16
17R[] = array of point
18 must be of length >= 2
19
20During initialization, the input point will be copied into R[1].
21The output point must be written in R[1] at the end.
22
23
24# Elliptic points
25
26It exists 3 types for the points on the elliptic curve:
27 - n: stands for "normal"
28 - a: stands for "ready for addition"
29 - d: stands for "only for differential elliptic operations"
30
31These 3 types can implemented with the same coordinates system on the same curve
32model or with different coordinates systems and/or different curve models.
33
34
35# Elliptic operations
36
37Depending on the type of the input point(s), the following elliptic operations
38are authorized:
39
40 | input | output |
41 op | points | type | point | type |
42------|---------|--------|-------|------|
43 DBL | P | n or a | 2 P | n |
44 DBLa | P | n or a | 2 P | a |
45 TPL | P | n or a | 3 P | n |
46 TPLa | P | n or a | 3 P | a |
47 ADD | P, Q | a | P + Q | n |
48 ADDa | P, Q | a | P + Q | a |
49 ADDd | P, Q | a | P + Q | d |
50 dDBL | P | d | 2 P | d |
51 dADD | P, Q, R | d | P + Q | d | with the condition that R = P - Q
52
53Note: it also exists a SUB variant for ADD, ADDa and ADDd
54
55
56# MISHMASH bytecode
57
58 0000nnnn Beginning of the MISHMASH bytecode
59 Allocate the array R with n+2 points
60 Must be the first byte of the bytecode
61 Cannot be used afterwards
62 Copy input point into R[1]
63 0001nnnn Beginning of a DBCHAIN block
64 Set R[0] <- R[n] (if n is 0, this is a no-op)
65 0010nnnn Beginning of a PRECOMP block
66 Set R[0] <- R[n] (if n is 0, this is a no-op)
67 1000nnnn Beginning of a PRAC block
68 Set R[0] <- R[n] (if n is 0, this is a no-op)
69 11111111 End of the MISHMASH bytecode
70 R[1] contains the results
71 Must be the last byte of the bytecode
72 Cannot be used before
73
74The first bit (= the most significant bit) of a byte describing the beginning of
75a block gives the type of the block: DBCHAIN and PRECOMP are block of type 0,
76PRAC is a block of type 1.
77Important: a block of type 0 cannot appear after a block of type 0
78
79block of type 0:
80 input is of type a
81 output is of type a or d (type d is only for the last block of type 0)
82block of type 1:
83 input is of type d
84 output is of type d
85
86MISHMASH bytecode:
87 input is of type a or d (type d means only block of type 1 can be used)
88 output is of type d
89
90
91# DBCHAIN block
92
93 01fsnnnn dddddddd R[f] <- 2^d R[0] +/- R[n]
94 op: d-1 DBL + 1 DBLa + ADDx
95 10fsnnnn tttttttt R[f] <- 3^t R[0] +/- R[n]
96 op: d-1 TPL + 1 TPLa + ADDx
97 11fsnnnn tttttttt dddddddd R[f] <- 2^d 3^t R[0] +/- R[n]
98 op: t TPL + d-1 DBL + 1 DBLa + ADDx
99
100 The sign is given by s: + if s=0, - if s=1
101 The f bit stands for 'final', it must be 1 only for the last byte of the
102 block.
103 The number of doublings d and the number of triplings t must be > 0.
104 ADDx = ADD if f = 0
105 ADDa if f = 1 and the next block is of type 0
106 ADDd if f = 1 and the next block is of type 1
107
108
109# PRECOMP block
110
111 00askkkk iiiijjjj R[k] <- R[i] +/- R[j]
112 op: ADDa if a == 1 else ADD
113 01a0kkkk dddddddd R[k] <- R[0] <- 2^d R[0]
114 op: d-1 DBL + DBLa if a == 1 else DBL
115 10a0kkkk tttttttt R[k] <- R[0] <- 3^t R[0]
116 op: t-1 TPL + TPLa if a == 1 else TPL
117 11111111 End of the block
118
119 The sign is given by s: + if s=0, - if s=1
120 The number of doublings d and the number of triplings t must be > 0.
121 In the last two cases, k can be 0 and the second assignment becomes a no-op.
122
123
124
125# PRAC block
126
127 Remarks:
128 - We always maintain R[0]-R[1] = R[2]
129 - This implies that we need len(R) >= 3
130 - In fact, we need len(R) >= 5, because two temporary points are needed
131
132
133 01101001 beginning a of sub-block [ 'i' in ASCII ]
134 R[2] <- R[1] <- R[0]
135 R[0] <- 2 R[0]
136 01110011 swap [ 's' in ASCII ]
137 R[0] <-> R[1]
138 01100110 end of sub-block [ 'f' in ASCII ]
139 R[0] <- R[0]+R[1]
140 01000110 end of sub-block and end of PRAC block [ 'F' in ASCII ]
141 R[1] <- R[0]+R[1]
142 00000001 Apply rule 1
143 00000010 Apply rule 2
144 00000011 Apply rule 3
145 00000100 Apply rule 4
146 00000101 Apply rule 5
147 00000110 Apply rule 6
148 00000111 Apply rule 7
149 00001000 Apply rule 8
150 00001001 Apply rule 9
151 00001010 Equivalent to 01101001 01100110 [ 'fi' in ASCII ]
152 00001011 Equivalent to 00000011 01110011 [ rule 3 then 's' in ASCII ]
153 00001100 Equivalent to 00000011 01101001 01100110
154 [ rule 3 then 'fi' in ASCII ]
155 00001101 Equivalent to 00001011 00001011 [ (rule 3 then 's' in ASCII)^2 ]
156
157
158
159Implementation
160==============
161
162# ECM
163
164elliptic point:
165 type n: projective point on "a=-1" twisted Edwards curves
166 type a: extended point on "a=-1" twisted Edwards curves
167 type d: XZ-only point on Montgomery curves
168
169
170# P+1
171
172element:
173 type n: not used
174 type a: not used
175 type d: element of the form x^n+1/x^n for n >= 0
176