git.iko.soy/urbit.org
on cf70879 help sign in
urbit.org/docs/programming/reference/zuse/rsa.md
399 lines 8.5 kB history raw
1------------------------------------------------------------------------
3### `++pram`
5Probable prime
7 ++ pram :: rabin-miller
8 |= a=@ ^- ?
9 ?: ?| =(0 (end 0 1 a))
10 =(1 a)
11 =+ b=1
12 |- ^- ?
13 ?: =(512 b)
14 |
15 ?|(=+(c=+((mul 2 b)) &(!=(a c) =(a (mul c (div a c))))) $(b +(b)))
16 ==
17 |
18 =+ ^= b
19 =+ [s=(dec a) t=0]
20 |- ^- [s=@ t=@]
21 ?: =(0 (end 0 1 s))
22 $(s (rsh 0 1 s), t +(t))
23 [s t]
24 ?> =((mul s.b (bex t.b)) (dec a))
25 =+ c=0
26 |- ^- ?
27 ?: =(c 64)
28 &
29 =+ d=(~(raw og (add c a)) (met 0 a))
30 =+ e=(~(exp fo a) s.b d)
31 ?& ?| =(1 e)
32 =+ f=0
33 |- ^- ?
34 ?: =(e (dec a))
35 &
36 ?: =(f (dec t.b))
37 |
38 $(e (~(pro fo a) e e), f +(f))
39 ==
40 $(c +(c))
41 ==
42 ::
44Probable prime test
46 ~zod/try=> (pram 31)
47 %.y
48 ~zod/try=> =+(a=2 |-(?:(=(a 31) ~ [i=(mod 31 a) t=$(a +(a))])))
49 ~[1 1 3 1 1 3 7 4 1 9 7 5 3 1 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1]
50 ~zod/try=> =+(a=2 |-(?:(=(a 31) ~ [i=(mod 30 a) t=$(a +(a))])))
51 ~[0 0 2 0 0 2 6 3 0 8 6 4 2 0 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0]
52 ~zod/try=> (pram 256)
53 %.n
54 ~zod/try=> (pram (dec (bex 127)))
55 %.y
57------------------------------------------------------------------------
59### `++ramp`
61`r-m` prime
63 ++ ramp :: make r-m prime
64 |= [a=@ b=(list ,@) c=@] ^- @ux :: [bits snags seed]
65 => .(c (shas %ramp c))
66 =+ d=_@
67 |-
68 ?: =((mul 100 a) d)
69 ~|(%ar-ramp !!)
70 =+ e=(~(raw og c) a)
71 ?: &((levy b |=(f=@ !=(1 (mod e f)))) (pram e))
72 e
73 $(c +(c), d (shax d))
74 ::
76Random `a` bit prime, which isn't 1 modulo a list of other numbers,
77using salt `c`.
79 ~zod/try=> (ramp 20 ~ %hamelok)
80 0xf.1f0d
81 ~zod/try=> (ramp 20 ~ %hameloe)
82 0x2.d341
83 ~zod/try=> (ramp 5 ~ %kole)
84 0x1f
85 ~zod/try=> (ramp 7 ~ %kole)
86 0x4f
87 ~zod/try=> (ramp 7 ~[0x4e] %kole)
88 0x43
89 ~zod/try=> `@uw`(ramp 128 ~ %late)
90 0w3y.irKIL.l-pp1.2CkG4.3lsTF
92------------------------------------------------------------------------
94### `++fo`
96Prime engine
98 ++ fo :: modulo prime
99 |_ a=@
101XX DO NOT RERUN GET.LS, THERE EXIST ARM COLLISIONS
103Core for performing arithmetic modulo a prime number
105 ~zod/try=> ~(. fo 79)
106 <7.get [@ud <373.jdd 100.kzl 1.ypj %164>]>
108------------------------------------------------------------------------
110### `++dif`
112Difference
114 ++ dif
115 |= [b=@ c=@]
116 (sit (sub (add a b) (sit c)))
117 ::
119Subtract
121 ~zod/try=> (~(dif fo 79) 10 5)
122 5
123 ~zod/try=> (~(dif fo 79) 5 10)
124 74
126------------------------------------------------------------------------
128### `++exp`
130Exponent
132 ++ exp
133 |= [b=@ c=@]
134 ?: =(0 b)
135 1
136 =+ d=$(b (rsh 0 1 b))
137 =+ e=(pro d d)
138 ?:(=(0 (end 0 1 b)) e (pro c e))
139 ::
141Exponent
143 ~zod/try=> (~(exp fo 79) 3 5)
144 46
146------------------------------------------------------------------------
148### `++fra`
150Divide
152 ++ fra
153 |= [b=@ c=@]
154 (pro b (inv c))
155 ::
157Divide
159 ~zod/try=> (~(fra fo 79) 20 4)
160 5
161 ~zod/try=> (~(fra fo 79) 7 11)
162 15
164------------------------------------------------------------------------
166### `++inv`
168Inverse
170 ++ inv
171 |= b=@
172 =+ c=(dul:si u:(egcd b a) a)
173 c
174 ::
176Multiplicative inverse
178 ~zod/try=> (~(inv fo 79) 12)
179 33
180 ~zod/try=> (~(pro fo 79) 12 33)
181 1
182 ~zod/try=> (~(inv fo 79) 0)
183 0
185------------------------------------------------------------------------
187### `++pro`
189Product
191 ++ pro
192 |= [b=@ c=@]
193 (sit (mul b c))
194 ::
196Product
198 ~zod/try=> (~(pro fo 79) 5 10)
199 50
200 ~zod/try=> (~(pro fo 79) 5 20)
201 21
203------------------------------------------------------------------------
205### `++sit`
207Bounds
209 ++ sit
210 |= b=@
211 (mod b a)
212 ::
214Bounds check
216 ~zod/try=> (~(sit fo 79) 9)
217 9
218 ~zod/try=> (~(sit fo 79) 99)
219 20
221------------------------------------------------------------------------
223### `++sum`
225Sum
227 ++ sum
228 |= [b=@ c=@]
229 (sit (add b c))
230 --
232Add
234 ~zod/try=> (~(sum fo 79) 9 9)
235 18
236 ~zod/try=> (~(sum fo 79) 70 9)
237 0
239------------------------------------------------------------------------
241### `++ga`
243 ++ ga :: GF (bex p.a)
244 |= a=[p=@ q=@ r=@] :: dim poly gen
245 =+ si=(bex p.a)
246 =+ ma=(dec si)
247 => |%
249RSA internals
251XX document
253------------------------------------------------------------------------
255### `++dif`
257 ++ dif :: add and sub
258 |= [b=@ c=@]
259 ~| [%dif-ga a]
260 ?> &((lth b si) (lth c si))
261 (mix b c)
262 ::
264XX document
266------------------------------------------------------------------------
268### `++dub`
270 ++ dub :: mul by x
271 |= b=@
272 ~| [%dub-ga a]
273 ?> (lth b si)
274 ?: =(1 (cut 0 [(dec p.a) 1] b))
275 (dif (sit q.a) (sit (lsh 0 1 b)))
276 (lsh 0 1 b)
277 ::
279XX document
281------------------------------------------------------------------------
283### `++pro`
285 ++ pro :: slow multiply
286 |= [b=@ c=@]
287 ?: =(0 b)
288 0
289 ?: =(1 (dis 1 b))
290 (dif c $(b (rsh 0 1 b), c (dub c)))
291 $(b (rsh 0 1 b), c (dub c))
292 ::
294XX document
296------------------------------------------------------------------------
298### `++toe`
300 ++ toe :: exp/log tables
301 =+ ^= nu
302 |= [b=@ c=@]
303 ^- (map ,@ ,@)
304 =+ d=*(map ,@ ,@)
305 |-
306 ?: =(0 c)
307 d
308 %= $
309 c (dec c)
310 d (~(put by d) c b)
311 ==
312 =+ [p=(nu 0 (bex p.a)) q=(nu ma ma)]
313 =+ [b=1 c=0]
314 |- ^- [p=(map ,@ ,@) q=(map ,@ ,@)]
315 ?: =(ma c)
316 [(~(put by p) c b) q]
317 %= $
318 b (pro r.a b)
319 c +(c)
320 p (~(put by p) c b)
321 q (~(put by q) b c)
322 ==
323 ::
325XX document
327------------------------------------------------------------------------
329### `++sit`
331 ++ sit :: reduce
332 |= b=@
333 (mod b (bex p.a))
334 --
336XX document
338------------------------------------------------------------------------
340### `++fra`
342 ++ fra :: divide
343 |= [b=@ c=@]
344 (pro b (inv c))
345 ::
347XX document
349------------------------------------------------------------------------
351### `++inv`
353 ++ inv :: invert
354 |= b=@
355 ~| [%inv-ga a]
356 =+ c=(~(get by q) b)
357 ?~ c !!
358 =+ d=(~(get by p) (sub ma u.c))
359 (need d)
360 ::
362XX document
364------------------------------------------------------------------------
366### `++pow`
368 ++ pow :: exponent
369 |= [b=@ c=@]
370 =+ [d=1 e=c f=0]
371 |-
372 ?: =(p.a f)
373 d
374 ?: =(1 (cut 0 [f 1] b))
375 $(d (pro d e), e (pro e e), f +(f))
376 $(e (pro e e), f +(f))
377 ::
379XX document
381------------------------------------------------------------------------
383### `++pro`
385 ++ pro :: multiply
386 |= [b=@ c=@]
387 ~| [%pro-ga a]
388 =+ d=(~(get by q) b)
389 ?~ d 0
390 =+ e=(~(get by q) c)
391 ?~ e 0
392 =+ f=(~(get by p) (mod (add u.d u.e) ma))
393 (need f)
394 --
396XX document
398------------------------------------------------------------------------