bignum.cpp@ 52018

Last change on this file since 52018 was 52018, checked in by vboxsync, 11 years ago
IPRT: Make RTMemSafer use the SUPR3 page allocation if available to allocate locked down memory. Change API to make allocation strategy tweakable to allow for pageable allocations where the support library is not available (build tools like bldRTSignTool) while still making sure the memory is non-pageable for sensitive data
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 61.1 KB

Line
1	/* $Id: bignum.cpp 52018 2014-07-14 19:44:01Z vboxsync $ */
2	/** @file
3	* IPRT - Big Integer Numbers.
4	*/
5
6	/*
7	* Copyright (C) 2006-2014 Oracle Corporation
8	*
9	* This file is part of VirtualBox Open Source Edition (OSE), as
10	* available from http://www.215389.xyz. This file is free software;
11	* you can redistribute it and/or modify it under the terms of the GNU
12	* General Public License (GPL) as published by the Free Software
13	* Foundation, in version 2 as it comes in the "COPYING" file of the
14	* VirtualBox OSE distribution. VirtualBox OSE is distributed in the
15	* hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
16	*
17	* The contents of this file may alternatively be used under the terms
18	* of the Common Development and Distribution License Version 1.0
19	* (CDDL) only, as it comes in the "COPYING.CDDL" file of the
20	* VirtualBox OSE distribution, in which case the provisions of the
21	* CDDL are applicable instead of those of the GPL.
22	*
23	* You may elect to license modified versions of this file under the
24	* terms and conditions of either the GPL or the CDDL or both.
25	*/
26
27
28	/*******************************************************************************
29	* Header Files *
30	*******************************************************************************/
31	#include "internal/iprt.h"
32	#include <iprt/bignum.h>
33
34	#include <iprt/asm.h>
35	#include <iprt/asm-math.h>
36	#include <iprt/err.h>
37	#include <iprt/mem.h>
38	#include <iprt/memsafer.h>
39	#include <iprt/string.h>
40
41
42	/** The max size (in bytes) of an elements array. */
43	#define RTBIGNUM_MAX_SIZE _4M
44
45
46	/**
47	* Scrambles a big number if required.
48	*
49	* @param pBigNum The big number.
50	*/
51	DECLINLINE(void) rtBigNumScramble(PRTBIGNUM pBigNum)
52	{
53	if (pBigNum->fSensitive)
54	{
55	AssertReturnVoid(!pBigNum->fCurScrambled);
56	if (pBigNum->pauElements)
57	{
58	int rc = RTMemSaferScramble(pBigNum->pauElements, pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE); AssertRC(rc);
59	pBigNum->fCurScrambled = RT_SUCCESS(rc);
60	}
61	else
62	pBigNum->fCurScrambled = true;
63	}
64	}
65
66
67	/**
68	* Unscrambles a big number if required.
69	*
70	* @returns IPRT status code.
71	* @param pBigNum The big number.
72	*/
73	DECLINLINE(int) rtBigNumUnscramble(PRTBIGNUM pBigNum)
74	{
75	if (pBigNum->fSensitive)
76	{
77	AssertReturn(pBigNum->fCurScrambled, VERR_INTERNAL_ERROR_2);
78	if (pBigNum->pauElements)
79	{
80	int rc = RTMemSaferUnscramble(pBigNum->pauElements, pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE); AssertRC(rc);
81	pBigNum->fCurScrambled = !RT_SUCCESS(rc);
82	return rc;
83	}
84	else
85	pBigNum->fCurScrambled = false;
86	}
87	return VINF_SUCCESS;
88	}
89
90
91	/**
92	* Getter function for pauElements which extends the array to infinity.
93	*
94	* @returns The element value.
95	* @param pBigNum The big number.
96	* @param iElement The element index.
97	*/
98	DECLINLINE(RTBIGNUMELEMENT) rtBigNumGetElement(PCRTBIGNUM pBigNum, uint32_t iElement)
99	{
100	if (iElement < pBigNum->cUsed)
101	return pBigNum->pauElements[iElement];
102	return 0;
103	}
104
105
106	/**
107	* Grows the pauElements array so it can fit at least @a cNewUsed entries.
108	*
109	* @returns IPRT status code.
110	* @param pBigNum The big number.
111	* @param cNewUsed The new cUsed value.
112	*/
113	static int rtBigNumGrow(PRTBIGNUM pBigNum, uint32_t cNewUsed)
114	{
115	uint32_t const cbOld = pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE;
116	uint32_t const cNew = RT_ALIGN_32(cNewUsed, 4);
117	uint32_t const cbNew = cNew * RTBIGNUM_ELEMENT_SIZE;
118	Assert(cbNew > cbOld);
119
120	void *pvNew = NULL;
121	if (pBigNum->fSensitive)
122	{
123	int rc = RTMemSaferReallocZEx(cbOld, pBigNum->pauElements, cbNew, &pvNew, RTMEMSAFER_ALLOC_EX_ALLOW_PAGEABLE_BACKING);
124	Assert(VALID_PTR(pvNew) \|\| RT_FAILURE(rc));
125	}
126	else
127	pvNew = RTMemRealloc(pBigNum->pauElements, cbNew);
128	if (RT_LIKELY(pvNew))
129	{
130	if (cbNew > cbOld)
131	RT_BZERO((char *)pvNew + cbOld, cbNew - cbOld);
132
133	pBigNum->pauElements = (RTBIGNUMELEMENT *)pvNew;
134	pBigNum->cUsed = cNewUsed;
135	pBigNum->cAllocated = cNew;
136	return VINF_SUCCESS;
137	}
138	return VERR_NO_MEMORY;
139	}
140
141
142	/**
143	* Changes the cUsed member, growing the pauElements array if necessary.
144	*
145	* No assumptions about the value of any added elements should be made. This
146	* method is mainly for resizing result values where the caller will repopulate
147	* the element values short after this call.
148	*
149	* @returns IPRT status code.
150	* @param pBigNum The big number.
151	* @param cNewUsed The new cUsed value.
152	*/
153	DECLINLINE(int) rtBigNumSetUsed(PRTBIGNUM pBigNum, uint32_t cNewUsed)
154	{
155	if (pBigNum->cAllocated >= cNewUsed)
156	{
157	pBigNum->cUsed = cNewUsed;
158	return VINF_SUCCESS;
159	}
160	return rtBigNumGrow(pBigNum, cNewUsed);
161	}
162
163	/**
164	* The slow part of rtBigNumEnsureElementPresent where we need to do actual zero
165	* extending.
166	*
167	* @returns IPRT status code.
168	* @param pBigNum The big number.
169	* @param iElement The element we wish to access.
170	*/
171	static int rtBigNumEnsureElementPresentSlow(PRTBIGNUM pBigNum, uint32_t iElement)
172	{
173	uint32_t const cOldUsed = pBigNum->cUsed;
174	int rc = rtBigNumSetUsed(pBigNum, iElement + 1);
175	if (RT_SUCCESS(rc))
176	{
177	RT_BZERO(&pBigNum->pauElements[cOldUsed], (iElement + 1 - cOldUsed) * RTBIGNUM_ELEMENT_SIZE);
178	return VINF_SUCCESS;
179	}
180	return rc;
181	}
182
183
184	/**
185	* Zero extends the element array to make sure a the specified element index is
186	* accessible.
187	*
188	* This is typically used with bit operations and self modifying methods. Any
189	* new elements added will be initialized to zero. The caller is responsible
190	* for there not being any trailing zero elements.
191	*
192	* The number must be unscrambled.
193	*
194	* @returns IPRT status code.
195	* @param pBigNum The big number.
196	* @param iElement The element we wish to access.
197	*/
198	DECLINLINE(int) rtBigNumEnsureElementPresent(PRTBIGNUM pBigNum, uint32_t iElement)
199	{
200	if (iElement < pBigNum->cUsed)
201	return VINF_SUCCESS;
202	return rtBigNumEnsureElementPresentSlow(pBigNum, iElement);
203	}
204
205
206	/**
207	* Strips zero elements from the magnitude value.
208	*
209	* @param pBigNum The big number to strip.
210	*/
211	static void rtBigNumStripTrailingZeros(PRTBIGNUM pBigNum)
212	{
213	uint32_t i = pBigNum->cUsed;
214	while (i > 0 && pBigNum->pauElements[i - 1] == 0)
215	i--;
216	pBigNum->cUsed = i;
217	}
218
219
220	/**
221	* Initialize the big number to zero.
222	*
223	* @returns @a pBigNum
224	* @param pBigNum The big number.
225	* @param fFlags The flags.
226	* @internal
227	*/
228	DECLINLINE(PRTBIGNUM) rtBigNumInitZeroInternal(PRTBIGNUM pBigNum, uint32_t fFlags)
229	{
230	RT_ZERO(*pBigNum);
231	pBigNum->fSensitive = RT_BOOL(fFlags & RTBIGNUMINIT_F_SENSITIVE);
232	return pBigNum;
233	}
234
235
236	/**
237	* Initialize the big number to zero from a template variable.
238	*
239	* @returns @a pBigNum
240	* @param pBigNum The big number.
241	* @param pTemplate The template big number.
242	* @internal
243	*/
244	DECLINLINE(PRTBIGNUM) rtBigNumInitZeroTemplate(PRTBIGNUM pBigNum, PCRTBIGNUM pTemplate)
245	{
246	RT_ZERO(*pBigNum);
247	pBigNum->fSensitive = pTemplate->fSensitive;
248	return pBigNum;
249	}
250
251
252	RTDECL(int) RTBigNumInit(PRTBIGNUM pBigNum, uint32_t fFlags, void const *pvRaw, size_t cbRaw)
253	{
254	/*
255	* Validate input.
256	*/
257	AssertPtrReturn(pBigNum, VERR_INVALID_POINTER);
258	AssertReturn(RT_BOOL(fFlags & RTBIGNUMINIT_F_ENDIAN_BIG) ^ RT_BOOL(fFlags & RTBIGNUMINIT_F_ENDIAN_LITTLE),
259	VERR_INVALID_PARAMETER);
260	AssertReturn(RT_BOOL(fFlags & RTBIGNUMINIT_F_UNSIGNED) ^ RT_BOOL(fFlags & RTBIGNUMINIT_F_SIGNED), VERR_INVALID_PARAMETER);
261	if (cbRaw)
262	AssertPtrReturn(pvRaw, VERR_INVALID_POINTER);
263
264	/*
265	* Initalize the big number to zero.
266	*/
267	rtBigNumInitZeroInternal(pBigNum, fFlags);
268
269	/*
270	* Strip the input and figure the sign flag.
271	*/
272	uint8_t const pb = (uint8_t const )pvRaw;
273	if (cbRaw)
274	{
275	if (fFlags & RTBIGNUMINIT_F_ENDIAN_LITTLE)
276	{
277	if (fFlags & RTBIGNUMINIT_F_UNSIGNED)
278	{
279	while (cbRaw > 0 && pb[cbRaw - 1] == 0)
280	cbRaw--;
281	}
282	else
283	{
284	if (pb[cbRaw - 1] >> 7)
285	{
286	pBigNum->fNegative = 1;
287	while (cbRaw > 1 && pb[cbRaw - 1] == 0xff)
288	cbRaw--;
289	}
290	else
291	while (cbRaw > 0 && pb[cbRaw - 1] == 0)
292	cbRaw--;
293	}
294	}
295	else
296	{
297	if (fFlags & RTBIGNUMINIT_F_UNSIGNED)
298	{
299	while (cbRaw > 0 && *pb == 0)
300	pb++, cbRaw--;
301	}
302	else
303	{
304	if (*pb >> 7)
305	{
306	pBigNum->fNegative = 1;
307	while (cbRaw > 1 && *pb == 0xff)
308	pb++, cbRaw--;
309	}
310	else
311	while (cbRaw > 0 && *pb == 0)
312	pb++, cbRaw--;
313	}
314	}
315	}
316
317	/*
318	* Allocate memory for the elements.
319	*/
320	size_t cbAligned = RT_ALIGN_Z(cbRaw, RTBIGNUM_ELEMENT_SIZE);
321	if (RT_UNLIKELY(cbAligned >= RTBIGNUM_MAX_SIZE))
322	return VERR_OUT_OF_RANGE;
323	pBigNum->cUsed = (uint32_t)cbAligned / RTBIGNUM_ELEMENT_SIZE;
324	if (pBigNum->cUsed)
325	{
326	pBigNum->cAllocated = RT_ALIGN_32(pBigNum->cUsed, 4);
327	if (pBigNum->fSensitive)
328	{
329	int rc = RTMemSaferAllocZEx((void *)&pBigNum->pauElements, pBigNum->cAllocated RTBIGNUM_ELEMENT_SIZE,
330	RTMEMSAFER_ALLOC_EX_ALLOW_PAGEABLE_BACKING);
331	Assert(VALID_PTR(pBigNum->pauElements) \|\| RT_FAILURE(rc));
332	}
333	else
334	pBigNum->pauElements = (RTBIGNUMELEMENT )RTMemAlloc(pBigNum->cAllocated RTBIGNUM_ELEMENT_SIZE);
335	if (RT_UNLIKELY(!pBigNum->pauElements))
336	return VERR_NO_MEMORY;
337
338	/*
339	* Initialize the array.
340	*/
341	uint32_t i = 0;
342	if (fFlags & RTBIGNUMINIT_F_ENDIAN_LITTLE)
343	{
344	while (cbRaw >= RTBIGNUM_ELEMENT_SIZE)
345	{
346	#if RTBIGNUM_ELEMENT_SIZE == 8
347	pBigNum->pauElements[i] = RT_MAKE_U64_FROM_U8(pb[0], pb[1], pb[2], pb[3], pb[4], pb[5], pb[6], pb[7]);
348	#elif RTBIGNUM_ELEMENT_SIZE == 4
349	pBigNum->pauElements[i] = RT_MAKE_U32_FROM_U8(pb[0], pb[1], pb[2], pb[3]);
350	#else
351	# error "Bad RTBIGNUM_ELEMENT_SIZE value"
352	#endif
353	i++;
354	pb += RTBIGNUM_ELEMENT_SIZE;
355	cbRaw -= RTBIGNUM_ELEMENT_SIZE;
356	}
357
358	if (cbRaw > 0)
359	{
360	RTBIGNUMELEMENT uLast = pBigNum->fNegative ? ~(RTBIGNUMELEMENT)0 : 0;
361	switch (cbRaw)
362	{
363	default: AssertFailed();
364	#if RTBIGNUM_ELEMENT_SIZE == 8
365	case 7: uLast = (uLast << 8) \| pb[6];
366	case 6: uLast = (uLast << 8) \| pb[5];
367	case 5: uLast = (uLast << 8) \| pb[4];
368	case 4: uLast = (uLast << 8) \| pb[3];
369	#endif
370	case 3: uLast = (uLast << 8) \| pb[2];
371	case 2: uLast = (uLast << 8) \| pb[1];
372	case 1: uLast = (uLast << 8) \| pb[0];
373	}
374	pBigNum->pauElements[i] = uLast;
375	}
376	}
377	else
378	{
379	pb += cbRaw;
380	while (cbRaw >= RTBIGNUM_ELEMENT_SIZE)
381	{
382	pb -= RTBIGNUM_ELEMENT_SIZE;
383	#if RTBIGNUM_ELEMENT_SIZE == 8
384	pBigNum->pauElements[i] = RT_MAKE_U64_FROM_U8(pb[7], pb[6], pb[5], pb[4], pb[3], pb[2], pb[1], pb[0]);
385	#elif RTBIGNUM_ELEMENT_SIZE == 4
386	pBigNum->pauElements[i] = RT_MAKE_U32_FROM_U8(pb[3], pb[2], pb[1], pb[0]);
387	#else
388	# error "Bad RTBIGNUM_ELEMENT_SIZE value"
389	#endif
390	i++;
391	cbRaw -= RTBIGNUM_ELEMENT_SIZE;
392	}
393
394	if (cbRaw > 0)
395	{
396	RTBIGNUMELEMENT uLast = pBigNum->fNegative ? ~(RTBIGNUMELEMENT)0 : 0;
397	pb -= cbRaw;
398	switch (cbRaw)
399	{
400	default: AssertFailed();
401	#if RTBIGNUM_ELEMENT_SIZE == 8
402	case 7: uLast = (uLast << 8) \| *pb++;
403	case 6: uLast = (uLast << 8) \| *pb++;
404	case 5: uLast = (uLast << 8) \| *pb++;
405	case 4: uLast = (uLast << 8) \| *pb++;
406	#endif
407	case 3: uLast = (uLast << 8) \| *pb++;
408	case 2: uLast = (uLast << 8) \| *pb++;
409	case 1: uLast = (uLast << 8) \| *pb++;
410	}
411	pBigNum->pauElements[i] = uLast;
412	}
413	}
414
415	/*
416	* If negative, negate it so we get a positive magnitude value in pauElements.
417	*/
418	if (pBigNum->fNegative)
419	{
420	pBigNum->pauElements[0] = 0U - pBigNum->pauElements[0];
421	for (i = 1; i < pBigNum->cUsed; i++)
422	pBigNum->pauElements[i] = 0U - pBigNum->pauElements[i] - 1U;
423	}
424	}
425
426	rtBigNumScramble(pBigNum);
427	return VINF_SUCCESS;
428	}
429
430
431	RTDECL(int) RTBigNumInitZero(PRTBIGNUM pBigNum, uint32_t fFlags)
432	{
433	AssertReturn(!(fFlags & ~RTBIGNUMINIT_F_SENSITIVE), VERR_INVALID_PARAMETER);
434	AssertPtrReturn(pBigNum, VERR_INVALID_POINTER);
435
436	rtBigNumInitZeroInternal(pBigNum, fFlags);
437	rtBigNumScramble(pBigNum);
438	return VINF_SUCCESS;
439	}
440
441
442	/**
443	* Internal clone function that assumes the caller takes care of scrambling.
444	*
445	* @returns IPRT status code.
446	* @param pBigNum The target number.
447	* @param pSrc The source number.
448	*/
449	static int rtBigNumCloneInternal(PRTBIGNUM pBigNum, PCRTBIGNUM pSrc)
450	{
451	Assert(!pSrc->fCurScrambled);
452	int rc = VINF_SUCCESS;
453
454	/*
455	* Copy over the data.
456	*/
457	RT_ZERO(*pBigNum);
458	pBigNum->fNegative = pSrc->fNegative;
459	pBigNum->fSensitive = pSrc->fSensitive;
460	pBigNum->cUsed = pSrc->cUsed;
461	if (pSrc->cUsed)
462	{
463	/* Duplicate the element array. */
464	pBigNum->cAllocated = RT_ALIGN_32(pBigNum->cUsed, 4);
465	if (pBigNum->fSensitive)
466	{
467	rc = RTMemSaferAllocZEx((void *)&pBigNum->pauElements, pBigNum->cAllocated RTBIGNUM_ELEMENT_SIZE,
468	RTMEMSAFER_ALLOC_EX_ALLOW_PAGEABLE_BACKING);
469	Assert(VALID_PTR(pBigNum->pauElements) \|\| RT_FAILURE(rc));
470	}
471	else
472	pBigNum->pauElements = (RTBIGNUMELEMENT )RTMemAlloc(pBigNum->cAllocated RTBIGNUM_ELEMENT_SIZE);
473	if (RT_LIKELY(pBigNum->pauElements))
474	memcpy(pBigNum->pauElements, pSrc->pauElements, pBigNum->cUsed * RTBIGNUM_ELEMENT_SIZE);
475	else
476	{
477	RT_ZERO(*pBigNum);
478	rc = VERR_NO_MEMORY;
479	}
480	}
481	return rc;
482	}
483
484
485	RTDECL(int) RTBigNumClone(PRTBIGNUM pBigNum, PCRTBIGNUM pSrc)
486	{
487	int rc = rtBigNumUnscramble((PRTBIGNUM)pSrc);
488	if (RT_SUCCESS(rc))
489	{
490	rc = rtBigNumCloneInternal(pBigNum, pSrc);
491	if (RT_SUCCESS(rc))
492	rtBigNumScramble(pBigNum);
493	rtBigNumScramble((PRTBIGNUM)pSrc);
494	}
495	return rc;
496	}
497
498
499	RTDECL(int) RTBigNumDestroy(PRTBIGNUM pBigNum)
500	{
501	if (pBigNum)
502	{
503	if (pBigNum->pauElements)
504	{
505	Assert(pBigNum->cAllocated > 0);
506	if (pBigNum->fSensitive)
507	{
508	RTMemSaferFree(pBigNum->pauElements, pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE);
509	RT_ZERO(*pBigNum);
510	}
511	RTMemFree(pBigNum->pauElements);
512	pBigNum->pauElements = NULL;
513	}
514	}
515	return VINF_SUCCESS;
516	}
517
518
519	RTDECL(int) RTBigNumAssign(PRTBIGNUM pDst, PCRTBIGNUM pSrc)
520	{
521	AssertReturn(pDst->fSensitive >= pSrc->fSensitive, VERR_BIGNUM_SENSITIVE_INPUT);
522	int rc = rtBigNumUnscramble(pDst);
523	if (RT_SUCCESS(rc))
524	{
525	rc = rtBigNumUnscramble((PRTBIGNUM)pSrc);
526	if (RT_SUCCESS(rc))
527	{
528	if ( pDst->fSensitive == pSrc->fSensitive
529	\|\| pDst->fSensitive)
530	{
531	if (pDst->cAllocated >= pSrc->cUsed)
532	{
533	pDst->cUsed = pSrc->cUsed;
534	pDst->fNegative = pSrc->fNegative;
535	memcpy(pDst->pauElements, pSrc->pauElements, pSrc->cUsed * RTBIGNUM_ELEMENT_SIZE);
536	}
537	else
538	{
539	rc = rtBigNumGrow(pDst, pSrc->cUsed);
540	if (RT_SUCCESS(rc))
541	{
542	pDst->fNegative = pSrc->fNegative;
543	memcpy(pDst->pauElements, pSrc->pauElements, pSrc->cUsed * RTBIGNUM_ELEMENT_SIZE);
544	}
545	}
546	}
547	else
548	rc = VERR_BIGNUM_SENSITIVE_INPUT;
549	rtBigNumScramble((PRTBIGNUM)pSrc);
550	}
551	rtBigNumScramble(pDst);
552	}
553	return rc;
554	}
555
556
557	static uint32_t rtBigNumElementBitCount(RTBIGNUMELEMENT uElement)
558	{
559	#if RTBIGNUM_ELEMENT_SIZE == 8
560	if (uElement >> 32)
561	return ASMBitLastSetU32((uint32_t)(uElement >> 32)) + 32;
562	return ASMBitLastSetU32((uint32_t)uElement);
563	#elif RTBIGNUM_ELEMENT_SIZE == 4
564	return ASMBitLastSetU32(uElement);
565	#else
566	# error "Bad RTBIGNUM_ELEMENT_SIZE value"
567	#endif
568	}
569
570
571	/**
572	* Same as RTBigNumBitWidth, except that it ignore the signed bit.
573	*
574	* The number must be unscrambled.
575	*
576	* @returns The effective width of the magnitude, in bits. Returns 0 if the
577	* value is zero.
578	* @param pBigNum The bit number.
579	*/
580	static uint32_t rtBigNumMagnitudeBitWidth(PCRTBIGNUM pBigNum)
581	{
582	uint32_t idxLast = pBigNum->cUsed;
583	if (idxLast)
584	{
585	idxLast--;
586	RTBIGNUMELEMENT uLast = pBigNum->pauElements[idxLast]; Assert(uLast);
587	return rtBigNumElementBitCount(uLast) + idxLast * RTBIGNUM_ELEMENT_BITS;
588	}
589	return 0;
590	}
591
592
593	RTDECL(uint32_t) RTBigNumBitWidth(PCRTBIGNUM pBigNum)
594	{
595	uint32_t idxLast = pBigNum->cUsed;
596	if (idxLast)
597	{
598	idxLast--;
599	rtBigNumUnscramble((PRTBIGNUM)pBigNum);
600	RTBIGNUMELEMENT uLast = pBigNum->pauElements[idxLast]; Assert(uLast);
601	rtBigNumScramble((PRTBIGNUM)pBigNum);
602	return rtBigNumElementBitCount(uLast) + idxLast * RTBIGNUM_ELEMENT_BITS + pBigNum->fNegative;
603	}
604	return 0;
605	}
606
607
608	RTDECL(uint32_t) RTBigNumByteWidth(PCRTBIGNUM pBigNum)
609	{
610	uint32_t cBits = RTBigNumBitWidth(pBigNum);
611	return (cBits + 7) / 8;
612	}
613
614
615	RTDECL(int) RTBigNumToBytesBigEndian(PCRTBIGNUM pBigNum, void *pvBuf, size_t cbWanted)
616	{
617	AssertPtrReturn(pvBuf, VERR_INVALID_POINTER);
618	AssertReturn(cbWanted > 0, VERR_INVALID_PARAMETER);
619
620	int rc = rtBigNumUnscramble((PRTBIGNUM)pBigNum);
621	if (RT_SUCCESS(rc))
622	{
623	rc = VINF_SUCCESS;
624	if (pBigNum->cUsed != 0)
625	{
626	uint8_t pbDst = (uint8_t )pvBuf;
627	pbDst += cbWanted - 1;
628	for (uint32_t i = 0; i < pBigNum->cUsed; i++)
629	{
630	RTBIGNUMELEMENT uElement = pBigNum->pauElements[i];
631	if (pBigNum->fNegative)
632	uElement = (RTBIGNUMELEMENT)0 - uElement - (i > 0);
633	if (cbWanted >= sizeof(uElement))
634	{
635	*pbDst-- = (uint8_t)uElement;
636	uElement >>= 8;
637	*pbDst-- = (uint8_t)uElement;
638	uElement >>= 8;
639	*pbDst-- = (uint8_t)uElement;
640	uElement >>= 8;
641	*pbDst-- = (uint8_t)uElement;
642	#if RTBIGNUM_ELEMENT_SIZE == 8
643	uElement >>= 8;
644	*pbDst-- = (uint8_t)uElement;
645	uElement >>= 8;
646	*pbDst-- = (uint8_t)uElement;
647	uElement >>= 8;
648	*pbDst-- = (uint8_t)uElement;
649	uElement >>= 8;
650	*pbDst-- = (uint8_t)uElement;
651	#elif RTBIGNUM_ELEMENT_SIZE != 4
652	# error "Bad RTBIGNUM_ELEMENT_SIZE value"
653	#endif
654	cbWanted -= sizeof(uElement);
655	}
656	else
657	{
658
659	uint32_t cBitsLeft = RTBIGNUM_ELEMENT_BITS;
660	while (cbWanted > 0)
661	{
662	*pbDst-- = (uint8_t)uElement;
663	uElement >>= 8;
664	cBitsLeft -= 8;
665	cbWanted--;
666	}
667	Assert(cBitsLeft > 0); Assert(cBitsLeft < RTBIGNUM_ELEMENT_BITS);
668	if ( i + 1 < pBigNum->cUsed
669	\|\| ( !pBigNum->fNegative
670	? uElement != 0
671	: uElement != ((RTBIGNUMELEMENT)1 << cBitsLeft) - 1U ) )
672	rc = VERR_BUFFER_OVERFLOW;
673	break;
674	}
675	}
676
677	/* Sign extend the number to the desired output size. */
678	if (cbWanted > 0)
679	memset(pbDst - cbWanted, pBigNum->fNegative ? 0 : 0xff, cbWanted);
680	}
681	else
682	RT_BZERO(pvBuf, cbWanted);
683	rtBigNumScramble((PRTBIGNUM)pBigNum);
684	}
685	return rc;
686	}
687
688
689	RTDECL(int) RTBigNumCompare(PRTBIGNUM pLeft, PRTBIGNUM pRight)
690	{
691	int rc = rtBigNumUnscramble(pLeft);
692	if (RT_SUCCESS(rc))
693	{
694	rc = rtBigNumUnscramble(pRight);
695	if (RT_SUCCESS(rc))
696	{
697	if (pLeft->fNegative == pRight->fNegative)
698	{
699	if (pLeft->cUsed == pRight->cUsed)
700	{
701	rc = 0;
702	uint32_t i = pLeft->cUsed;
703	while (i-- > 0)
704	if (pLeft->pauElements[i] != pRight->pauElements[i])
705	{
706	rc = pLeft->pauElements[i] < pRight->pauElements[i] ? -1 : 1;
707	break;
708	}
709	if (pLeft->fNegative)
710	rc = -rc;
711	}
712	else
713	rc = !pLeft->fNegative
714	? pLeft->cUsed < pRight->cUsed ? -1 : 1
715	: pLeft->cUsed < pRight->cUsed ? 1 : -1;
716	}
717	else
718	rc = pLeft->fNegative ? -1 : 1;
719
720	rtBigNumScramble(pRight);
721	}
722	rtBigNumScramble(pLeft);
723	}
724	return rc;
725	}
726
727
728	RTDECL(int) RTBigNumCompareWithU64(PRTBIGNUM pLeft, uint64_t uRight)
729	{
730	int rc = rtBigNumUnscramble(pLeft);
731	if (RT_SUCCESS(rc))
732	{
733	if (!pLeft->fNegative)
734	{
735	if (pLeft->cUsed * RTBIGNUM_ELEMENT_SIZE <= sizeof(uRight))
736	{
737	if (pLeft->cUsed == 0)
738	rc = uRight == 0 ? 0 : -1;
739	else
740	{
741	#if RTBIGNUM_ELEMENT_SIZE == 8
742	uint64_t uLeft = rtBigNumGetElement(pLeft, 0);
743	if (uLeft < uRight)
744	rc = -1;
745	else
746	rc = uLeft == uRight ? 0 : 1;
747	#elif RTBIGNUM_ELEMENT_SIZE == 4
748	uint32_t uSubLeft = rtBigNumGetElement(pLeft, 1);
749	uint32_t uSubRight = uRight >> 32;
750	if (uSubLeft == uSubRight)
751	{
752	uSubLeft = rtBigNumGetElement(pLeft, 0);
753	uSubRight = (uint32_t)uRight;
754	}
755	if (uSubLeft < uSubRight)
756	rc = -1;
757	else
758	rc = uSubLeft == uSubRight ? 0 : 1;
759	#else
760	# error "Bad RTBIGNUM_ELEMENT_SIZE value"
761	#endif
762	}
763	}
764	else
765	rc = 1;
766	}
767	else
768	rc = -1;
769	rtBigNumScramble(pLeft);
770	}
771	return rc;
772	}
773
774
775	RTDECL(int) RTBigNumCompareWithS64(PRTBIGNUM pLeft, int64_t iRight)
776	{
777	int rc = rtBigNumUnscramble(pLeft);
778	if (RT_SUCCESS(rc))
779	{
780	if (pLeft->fNegative == (iRight < 0))
781	{
782	if (pLeft->cUsed * RTBIGNUM_ELEMENT_SIZE <= sizeof(iRight))
783	{
784	uint64_t uRightMagn = !pLeft->fNegative ? (uint64_t)iRight : (uint64_t)-iRight;
785	#if RTBIGNUM_ELEMENT_SIZE == 8
786	uint64_t uLeft = rtBigNumGetElement(pLeft, 0);
787	if (uLeft < uRightMagn)
788	rc = -1;
789	else
790	rc = uLeft == (uint64_t)uRightMagn ? 0 : 1;
791	#elif RTBIGNUM_ELEMENT_SIZE == 4
792	uint32_t uSubLeft = rtBigNumGetElement(pLeft, 1);
793	uint32_t uSubRight = uRightMagn >> 32;
794	if (uSubLeft == uSubRight)
795	{
796	uSubLeft = rtBigNumGetElement(pLeft, 0);
797	uSubRight = (uint32_t)uRightMagn;
798	}
799	if (uSubLeft < uSubRight)
800	rc = -1;
801	else
802	rc = uSubLeft == uSubRight ? 0 : 1;
803	#else
804	# error "Bad RTBIGNUM_ELEMENT_SIZE value"
805	#endif
806	if (pLeft->fNegative)
807	rc = -rc;
808	}
809	else
810	rc = pLeft->fNegative ? -1 : 1;
811	}
812	else
813	rc = pLeft->fNegative ? -1 : 1;
814	rtBigNumScramble(pLeft);
815	}
816	return rc;
817	}
818
819
820	#define RTBIGNUMELEMENT_HALF_MASK ( ((RTBIGNUMELEMENT)1 << (RTBIGNUM_ELEMENT_BITS / 2)) - (RTBIGNUMELEMENT)1)
821	#define RTBIGNUMELEMENT_LO_HALF(a_uElement) ( (RTBIGNUMELEMENT_HALF_MASK) & (a_uElement) )
822	#define RTBIGNUMELEMENT_HI_HALF(a_uElement) ( (a_uElement) >> (RTBIGNUM_ELEMENT_BITS / 2) )
823
824
825	/**
826	* Compares the magnitude values of two big numbers.
827	*
828	* @retval -1 if pLeft is smaller than pRight.
829	* @retval 0 if pLeft is equal to pRight.
830	* @retval 1 if pLeft is larger than pRight.
831	* @param pLeft The left side number.
832	* @param pRight The right side number.
833	*/
834	static int rtBigNumMagnitudeCompare(PCRTBIGNUM pLeft, PCRTBIGNUM pRight)
835	{
836	Assert(!pLeft->fCurScrambled); Assert(!pRight->fCurScrambled);
837	int rc;
838	uint32_t i = pLeft->cUsed;
839	if (i == pRight->cUsed)
840	{
841	rc = 0;
842	while (i-- > 0)
843	if (pLeft->pauElements[i] != pRight->pauElements[i])
844	{
845	rc = pLeft->pauElements[i] < pRight->pauElements[i] ? -1 : 1;
846	break;
847	}
848	}
849	else
850	rc = i < pRight->cUsed ? -1 : 1;
851	return rc;
852	}
853
854
855	/**
856	* Does addition with carry.
857	*
858	* This is a candidate for inline assembly on some platforms.
859	*
860	* @returns The result (the sum)
861	* @param uAugend What to add to.
862	* @param uAddend What to add to it.
863	* @param pfCarry Where to read the input carry and return the output
864	* carry.
865	*/
866	DECLINLINE(RTBIGNUMELEMENT) rtBigNumElementAddWithCarry(RTBIGNUMELEMENT uAugend, RTBIGNUMELEMENT uAddend,
867	RTBIGNUMELEMENT *pfCarry)
868	{
869	RTBIGNUMELEMENT uRet = uAugend + uAddend + *pfCarry;
870
871	/* Determin carry the expensive way. */
872	RTBIGNUMELEMENT uTmp = RTBIGNUMELEMENT_HI_HALF(uAugend) + RTBIGNUMELEMENT_HI_HALF(uAddend);
873	if (uTmp < RTBIGNUMELEMENT_HALF_MASK)
874	*pfCarry = 0;
875	else
876	*pfCarry = uTmp > RTBIGNUMELEMENT_HALF_MASK
877	\|\| RTBIGNUMELEMENT_LO_HALF(uAugend) + RTBIGNUMELEMENT_LO_HALF(uAddend) + *pfCarry
878	> RTBIGNUMELEMENT_HALF_MASK;
879	return uRet;
880	}
881
882
883	/**
884	* Adds two magnitudes and stores them into a third.
885	*
886	* All variables must be unscrambled. The sign flag is not considered nor
887	* touched.
888	*
889	* @returns IPRT status code.
890	* @param pResult The resultant.
891	* @param pAugend To whom it shall be addede.
892	* @param pAddend The nombre to addede.
893	*/
894	static int rtBigNumMagnitudeAdd(PRTBIGNUM pResult, PCRTBIGNUM pAugend, PCRTBIGNUM pAddend)
895	{
896	Assert(!pResult->fCurScrambled); Assert(!pAugend->fCurScrambled); Assert(!pAddend->fCurScrambled);
897	Assert(pResult != pAugend); Assert(pResult != pAddend);
898
899	uint32_t cElements = RT_MAX(pAugend->cUsed, pAddend->cUsed);
900	int rc = rtBigNumSetUsed(pResult, cElements);
901	if (RT_SUCCESS(rc))
902	{
903	/*
904	* The primitive way, requires at least two additions for each entry
905	* without machine code help.
906	*/
907	RTBIGNUMELEMENT fCarry = 0;
908	for (uint32_t i = 0; i < cElements; i++)
909	pResult->pauElements[i] = rtBigNumElementAddWithCarry(rtBigNumGetElement(pAugend, i),
910	rtBigNumGetElement(pAddend, i),
911	&fCarry);
912	if (fCarry)
913	{
914	rc = rtBigNumSetUsed(pResult, cElements + 1);
915	if (RT_SUCCESS(rc))
916	pResult->pauElements[cElements++] = 1;
917	}
918	Assert(pResult->cUsed == cElements \|\| RT_FAILURE_NP(rc));
919	}
920
921	return rc;
922	}
923
924
925	/**
926	* Does addition with borrow.
927	*
928	* This is a candidate for inline assembly on some platforms.
929	*
930	* @returns The result (the sum)
931	* @param uMinuend What to subtract from.
932	* @param uSubtrahend What to subtract.
933	* @param pfBorrow Where to read the input borrow and return the output
934	* borrow.
935	*/
936	DECLINLINE(RTBIGNUMELEMENT) rtBigNumElementSubWithBorrow(RTBIGNUMELEMENT uMinuend, RTBIGNUMELEMENT uSubtrahend,
937	RTBIGNUMELEMENT *pfBorrow)
938	{
939	RTBIGNUMELEMENT uRet = uMinuend - uSubtrahend - *pfBorrow;
940
941	/* Figure out if we borrowed. */
942	pfBorrow = !pfBorrow ? uMinuend < uSubtrahend : uMinuend <= uSubtrahend;
943	return uRet;
944	}
945
946
947	/**
948	* Substracts a smaller (or equal) magnitude from another one and stores it into
949	* a third.
950	*
951	* All variables must be unscrambled. The sign flag is not considered nor
952	* touched. For this reason, the @a pMinuend must be larger or equal to @a
953	* pSubtrahend.
954	*
955	* @returns IPRT status code.
956	* @param pResult There to store the result.
957	* @param pMinuend What to subtract from.
958	* @param pSubtrahend What to subtract.
959	*/
960	static int rtBigNumMagnitudeSub(PRTBIGNUM pResult, PCRTBIGNUM pMinuend, PCRTBIGNUM pSubtrahend)
961	{
962	Assert(!pResult->fCurScrambled); Assert(!pMinuend->fCurScrambled); Assert(!pSubtrahend->fCurScrambled);
963	Assert(pResult != pMinuend); Assert(pResult != pSubtrahend);
964	Assert(pMinuend->cUsed >= pSubtrahend->cUsed);
965
966	int rc = rtBigNumSetUsed(pResult, pMinuend->cUsed);
967	if (RT_SUCCESS(rc))
968	{
969	/*
970	* The primitive way, as usual.
971	*/
972	RTBIGNUMELEMENT fBorrow = 0;
973	for (uint32_t i = 0; i < pMinuend->cUsed; i++)
974	pResult->pauElements[i] = rtBigNumElementSubWithBorrow(pMinuend->pauElements[i],
975	rtBigNumGetElement(pSubtrahend, i),
976	&fBorrow);
977	Assert(fBorrow == 0);
978
979	/*
980	* Trim the result.
981	*/
982	rtBigNumStripTrailingZeros(pResult);
983	}
984
985	return rc;
986	}
987
988
989	/**
990	* Substracts a smaller (or equal) magnitude from another one and stores the
991	* result into the first.
992	*
993	* All variables must be unscrambled. The sign flag is not considered nor
994	* touched. For this reason, the @a pMinuendResult must be larger or equal to
995	* @a pSubtrahend.
996	*
997	* @param pMinuendResult What to subtract from and return as result.
998	* @param pSubtrahend What to subtract.
999	*/
1000	static void rtBigNumMagnitudeSubThis(PRTBIGNUM pMinuendResult, PCRTBIGNUM pSubtrahend)
1001	{
1002	Assert(!pMinuendResult->fCurScrambled); Assert(!pSubtrahend->fCurScrambled);
1003	Assert(pMinuendResult != pSubtrahend);
1004	Assert(pMinuendResult->cUsed >= pSubtrahend->cUsed);
1005
1006	/*
1007	* The primitive way, as usual.
1008	*/
1009	RTBIGNUMELEMENT fBorrow = 0;
1010	for (uint32_t i = 0; i < pMinuendResult->cUsed; i++)
1011	pMinuendResult->pauElements[i] = rtBigNumElementSubWithBorrow(pMinuendResult->pauElements[i],
1012	rtBigNumGetElement(pSubtrahend, i),
1013	&fBorrow);
1014	Assert(fBorrow == 0);
1015
1016	/*
1017	* Trim the result.
1018	*/
1019	rtBigNumStripTrailingZeros(pMinuendResult);
1020	}
1021
1022
1023	RTDECL(int) RTBigNumAdd(PRTBIGNUM pResult, PCRTBIGNUM pAugend, PCRTBIGNUM pAddend)
1024	{
1025	Assert(pResult != pAugend); Assert(pResult != pAddend);
1026	AssertReturn(pResult->fSensitive >= (pAugend->fSensitive \| pAddend->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1027
1028	int rc = rtBigNumUnscramble(pResult);
1029	if (RT_SUCCESS(rc))
1030	{
1031	rc = rtBigNumUnscramble((PRTBIGNUM)pAugend);
1032	if (RT_SUCCESS(rc))
1033	{
1034	rc = rtBigNumUnscramble((PRTBIGNUM)pAddend);
1035	if (RT_SUCCESS(rc))
1036	{
1037	/*
1038	* Same sign: Add magnitude, keep sign.
1039	* 1 + 1 = 2
1040	* (-1) + (-1) = -2
1041	*/
1042	if (pAugend->fNegative == pAddend->fNegative)
1043	{
1044	pResult->fNegative = pAugend->fNegative;
1045	rc = rtBigNumMagnitudeAdd(pResult, pAugend, pAddend);
1046	}
1047	/*
1048	* Different sign: Subtract smaller from larger, keep sign of larger.
1049	* (-5) + 3 = -2
1050	* 5 + (-3) = 2
1051	* (-1) + 3 = 2
1052	* 1 + (-3) = -2
1053	*/
1054	else if (rtBigNumMagnitudeCompare(pAugend, pAddend) >= 0)
1055	{
1056	pResult->fNegative = pAugend->fNegative;
1057	rc = rtBigNumMagnitudeSub(pResult, pAugend, pAddend);
1058	if (!pResult->cUsed)
1059	pResult->fNegative = 0;
1060	}
1061	else
1062	{
1063	pResult->fNegative = pAddend->fNegative;
1064	rc = rtBigNumMagnitudeSub(pResult, pAddend, pAugend);
1065	}
1066	rtBigNumScramble((PRTBIGNUM)pAddend);
1067	}
1068	rtBigNumScramble((PRTBIGNUM)pAugend);
1069	}
1070	rtBigNumScramble(pResult);
1071	}
1072	return rc;
1073	}
1074
1075
1076	RTDECL(int) RTBigNumSubtract(PRTBIGNUM pResult, PCRTBIGNUM pMinuend, PCRTBIGNUM pSubtrahend)
1077	{
1078	Assert(pResult != pMinuend); Assert(pResult != pSubtrahend);
1079	AssertReturn(pResult->fSensitive >= (pMinuend->fSensitive \| pSubtrahend->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1080
1081	int rc = rtBigNumUnscramble(pResult);
1082	if (RT_SUCCESS(rc))
1083	{
1084	if (pMinuend != pSubtrahend)
1085	{
1086	rc = rtBigNumUnscramble((PRTBIGNUM)pMinuend);
1087	if (RT_SUCCESS(rc))
1088	{
1089	rc = rtBigNumUnscramble((PRTBIGNUM)pSubtrahend);
1090	if (RT_SUCCESS(rc))
1091	{
1092	/*
1093	* Different sign: Add magnitude, keep sign of first.
1094	* 1 - (-2) == 3
1095	* -1 - 2 == -3
1096	*/
1097	if (pMinuend->fNegative != pSubtrahend->fNegative)
1098	{
1099	pResult->fNegative = pMinuend->fNegative;
1100	rc = rtBigNumMagnitudeAdd(pResult, pMinuend, pSubtrahend);
1101	}
1102	/*
1103	* Same sign, minuend has greater or equal absolute value: Subtract, keep sign of first.
1104	* 10 - 7 = 3
1105	*/
1106	else if (rtBigNumMagnitudeCompare(pMinuend, pSubtrahend) >= 0)
1107	{
1108	pResult->fNegative = pMinuend->fNegative;
1109	rc = rtBigNumMagnitudeSub(pResult, pMinuend, pSubtrahend);
1110	}
1111	/*
1112	* Same sign, subtrahend is larger: Reverse and subtract, invert sign of first.
1113	* 7 - 10 = -3
1114	* -1 - (-3) = 2
1115	*/
1116	else
1117	{
1118	pResult->fNegative = !pMinuend->fNegative;
1119	rc = rtBigNumMagnitudeSub(pResult, pSubtrahend, pMinuend);
1120	}
1121	rtBigNumScramble((PRTBIGNUM)pSubtrahend);
1122	}
1123	rtBigNumScramble((PRTBIGNUM)pMinuend);
1124	}
1125	}
1126	else
1127	{
1128	/* zero. */
1129	pResult->fNegative = 0;
1130	pResult->cUsed = 0;
1131	}
1132	rtBigNumScramble(pResult);
1133	}
1134	return rc;
1135	}
1136
1137
1138	RTDECL(int) RTBigNumNegateThis(PRTBIGNUM pThis)
1139	{
1140	pThis->fNegative = !pThis->fNegative;
1141	return VINF_SUCCESS;
1142	}
1143
1144
1145	RTDECL(int) RTBigNumNegate(PRTBIGNUM pResult, PCRTBIGNUM pBigNum)
1146	{
1147	int rc = RTBigNumAssign(pResult, pBigNum);
1148	if (RT_SUCCESS(rc))
1149	rc = RTBigNumNegateThis(pResult);
1150	return rc;
1151	}
1152
1153
1154	/**
1155	* Multiplies the magnitudes of two values, letting the caller care about the
1156	* sign bit.
1157	*
1158	* @returns IPRT status code.
1159	* @param pResult Where to store the result.
1160	* @param pMultiplicand The first value.
1161	* @param pMultiplier The second value.
1162	*/
1163	static int rtBigNumMagnitudeMultiply(PRTBIGNUM pResult, PCRTBIGNUM pMultiplicand, PCRTBIGNUM pMultiplier)
1164	{
1165	Assert(pResult != pMultiplicand); Assert(pResult != pMultiplier);
1166	Assert(!pResult->fCurScrambled); Assert(!pMultiplicand->fCurScrambled); Assert(!pMultiplier->fCurScrambled);
1167
1168	/*
1169	* Multiplication involving zero is zero.
1170	*/
1171	if (!pMultiplicand->cUsed \|\| !pMultiplier->cUsed)
1172	{
1173	pResult->fNegative = 0;
1174	pResult->cUsed = 0;
1175	return VINF_SUCCESS;
1176	}
1177
1178	/*
1179	* Allocate a result array that is the sum of the two factors, initialize
1180	* it to zero.
1181	*/
1182	uint32_t cMax = pMultiplicand->cUsed + pMultiplier->cUsed;
1183	int rc = rtBigNumSetUsed(pResult, cMax);
1184	if (RT_SUCCESS(rc))
1185	{
1186	RT_BZERO(pResult->pauElements, pResult->cUsed * RTBIGNUM_ELEMENT_SIZE);
1187
1188	for (uint32_t i = 0; i < pMultiplier->cUsed; i++)
1189	{
1190	RTBIGNUMELEMENT uMultiplier = pMultiplier->pauElements[i];
1191	for (uint32_t j = 0; j < pMultiplicand->cUsed; j++)
1192	{
1193	RTBIGNUMELEMENT uHi;
1194	RTBIGNUMELEMENT uLo;
1195	#if RTBIGNUM_ELEMENT_SIZE == 4
1196	uint64_t u64 = ASMMult2xU32RetU64(pMultiplicand->pauElements[j], uMultiplier);
1197	uLo = (uint32_t)u64;
1198	uHi = u64 >> 32;
1199	#elif RTBIGNUM_ELEMENT_SIZE == 8
1200	uLo = ASMMult2xU64Ret2xU64(pMultiplicand->pauElements[j], uMultiplier, &uHi);
1201	#else
1202	# error "Invalid RTBIGNUM_ELEMENT_SIZE value"
1203	#endif
1204	RTBIGNUMELEMENT fCarry = 0;
1205	uint64_t k = i + j;
1206	pResult->pauElements[k] = rtBigNumElementAddWithCarry(pResult->pauElements[k], uLo, &fCarry);
1207	k++;
1208	pResult->pauElements[k] = rtBigNumElementAddWithCarry(pResult->pauElements[k], uHi, &fCarry);
1209	while (fCarry)
1210	{
1211	k++;
1212	pResult->pauElements[k] = rtBigNumElementAddWithCarry(pResult->pauElements[k], 0, &fCarry);
1213	}
1214	Assert(k < cMax);
1215	}
1216	}
1217
1218	/* It's possible we overestimated the output size by 1 element. */
1219	rtBigNumStripTrailingZeros(pResult);
1220	}
1221	return rc;
1222	}
1223
1224
1225	RTDECL(int) RTBigNumMultiply(PRTBIGNUM pResult, PCRTBIGNUM pMultiplicand, PCRTBIGNUM pMultiplier)
1226	{
1227	Assert(pResult != pMultiplicand); Assert(pResult != pMultiplier);
1228	AssertReturn(pResult->fSensitive >= (pMultiplicand->fSensitive \| pMultiplier->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1229
1230	int rc = rtBigNumUnscramble(pResult);
1231	if (RT_SUCCESS(rc))
1232	{
1233	rc = rtBigNumUnscramble((PRTBIGNUM)pMultiplicand);
1234	if (RT_SUCCESS(rc))
1235	{
1236	rc = rtBigNumUnscramble((PRTBIGNUM)pMultiplier);
1237	if (RT_SUCCESS(rc))
1238	{
1239	/*
1240	* The sign values follow XOR rules:
1241	* -1 * 1 = -1; 1 ^ 0 = 1
1242	* 1 * -1 = -1; 1 ^ 0 = 1
1243	* -1 * -1 = 1; 1 ^ 1 = 0
1244	* 1 * 1 = 1; 0 ^ 0 = 0
1245	*/
1246	pResult->fNegative = pMultiplicand->fNegative ^ pMultiplier->fNegative;
1247	rc = rtBigNumMagnitudeMultiply(pResult, pMultiplicand, pMultiplier);
1248
1249	rtBigNumScramble((PRTBIGNUM)pMultiplier);
1250	}
1251	rtBigNumScramble((PRTBIGNUM)pMultiplicand);
1252	}
1253	rtBigNumScramble(pResult);
1254	}
1255	return rc;
1256	}
1257
1258
1259	/**
1260	* Copies the magnitude of on number (@a pSrc) to another (@a pBigNum).
1261	*
1262	* The variables must be unscrambled. The sign flag is not considered nor
1263	* touched.
1264	*
1265	* @returns IPRT status code.
1266	* @param pDst The destination number.
1267	* @param pSrc The source number.
1268	*/
1269	DECLINLINE(int) rtBigNumMagnitudeCopy(PRTBIGNUM pDst, PCRTBIGNUM pSrc)
1270	{
1271	int rc = rtBigNumSetUsed(pDst, pSrc->cUsed);
1272	if (RT_SUCCESS(rc))
1273	memcpy(pDst->pauElements, pSrc->pauElements, pSrc->cUsed * RTBIGNUM_ELEMENT_SIZE);
1274	return rc;
1275	}
1276
1277
1278	/**
1279	* Clears a bit in the magnitude of @a pBigNum.
1280	*
1281	* The variables must be unscrambled.
1282	*
1283	* @param pBigNum The big number.
1284	* @param iBit The bit to clear (0-based).
1285	*/
1286	DECLINLINE(void) rtBigNumMagnitudeClearBit(PRTBIGNUM pBigNum, uint32_t iBit)
1287	{
1288	uint32_t iElement = iBit / RTBIGNUM_ELEMENT_BITS;
1289	if (iElement < pBigNum->cUsed)
1290	{
1291	pBigNum->pauElements[iElement] &= ~RTBIGNUM_ELEMENT_BIT(iBit);
1292	if (iElement + 1 == pBigNum->cUsed && !pBigNum->pauElements[iElement])
1293	rtBigNumStripTrailingZeros(pBigNum);
1294	}
1295	}
1296
1297
1298	/**
1299	* Sets a bit in the magnitude of @a pBigNum.
1300	*
1301	* The variables must be unscrambled.
1302	*
1303	* @returns IPRT status code.
1304	* @param pBigNum The big number.
1305	* @param iBit The bit to clear (0-based).
1306	*/
1307	DECLINLINE(int) rtBigNumMagnitudeSetBit(PRTBIGNUM pBigNum, uint32_t iBit)
1308	{
1309	uint32_t iElement = iBit / RTBIGNUM_ELEMENT_BITS;
1310	int rc = rtBigNumEnsureElementPresent(pBigNum, iElement);
1311	if (RT_SUCCESS(rc))
1312	{
1313	pBigNum->pauElements[iElement] \|= RTBIGNUM_ELEMENT_BIT(iBit);
1314	return VINF_SUCCESS;
1315	}
1316	return rc;
1317	}
1318
1319
1320	/**
1321	* Writes a bit in the magnitude of @a pBigNum.
1322	*
1323	* The variables must be unscrambled.
1324	*
1325	* @returns IPRT status code.
1326	* @param pBigNum The big number.
1327	* @param iBit The bit to write (0-based).
1328	* @param fValue The bit value.
1329	*/
1330	DECLINLINE(int) rtBigNumMagnitudeWriteBit(PRTBIGNUM pBigNum, uint32_t iBit, bool fValue)
1331	{
1332	if (fValue)
1333	return rtBigNumMagnitudeSetBit(pBigNum, iBit);
1334	rtBigNumMagnitudeClearBit(pBigNum, iBit);
1335	return VINF_SUCCESS;
1336	}
1337
1338
1339	/**
1340	* Returns the given magnitude bit.
1341	*
1342	* The variables must be unscrambled.
1343	*
1344	* @returns The bit value (1 or 0).
1345	* @param pBigNum The big number.
1346	* @param iBit The bit to return (0-based).
1347	*/
1348	DECLINLINE(RTBIGNUMELEMENT) rtBigNumMagnitudeGetBit(PCRTBIGNUM pBigNum, uint32_t iBit)
1349	{
1350	uint32_t iElement = iBit / RTBIGNUM_ELEMENT_BITS;
1351	if (iElement < pBigNum->cUsed)
1352	return (pBigNum->pauElements[iElement] >> iBit) & 1;
1353	return 0;
1354	}
1355
1356
1357	/**
1358	* Shifts the magnitude left by one.
1359	*
1360	* The variables must be unscrambled.
1361	*
1362	* @returns IPRT status code.
1363	* @param pBigNum The big number.
1364	* @param uCarry The value to shift in at the bottom.
1365	*/
1366	DECLINLINE(int) rtBigNumMagnitudeShiftLeftOne(PRTBIGNUM pBigNum, RTBIGNUMELEMENT uCarry)
1367	{
1368	Assert(uCarry <= 1);
1369
1370	/* Do the shifting. */
1371	uint32_t cUsed = pBigNum->cUsed;
1372	for (uint32_t i = 0; i < cUsed; i++)
1373	{
1374	RTBIGNUMELEMENT uTmp = pBigNum->pauElements[i];
1375	pBigNum->pauElements[i] = (uTmp << 1) \| uCarry;
1376	uCarry = uTmp >> (RTBIGNUM_ELEMENT_BITS - 1);
1377	}
1378
1379	/* If we still carry a bit, we need to increase the size. */
1380	if (uCarry)
1381	{
1382	int rc = rtBigNumSetUsed(pBigNum, cUsed + 1);
1383	pBigNum->pauElements[cUsed] = uCarry;
1384	}
1385
1386	return VINF_SUCCESS;
1387	}
1388
1389
1390	/**
1391	* Divides the magnitudes of two values, letting the caller care about the sign
1392	* bit.
1393	*
1394	* All variables must be unscrambled. The sign flag is not considered nor
1395	* touched, this means the caller have to check for zero outputs.
1396	*
1397	* @returns IPRT status code.
1398	* @param pQuotient Where to return the quotient.
1399	* @param pRemainder Where to return the reminder.
1400	* @param pDividend What to divide.
1401	* @param pDivisor What to divide by.
1402	*/
1403	static int rtBigNumMagnitudeDivide(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
1404	{
1405	Assert(pQuotient != pDividend); Assert(pQuotient != pDivisor); Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor); Assert(pRemainder != pQuotient);
1406	Assert(!pQuotient->fCurScrambled); Assert(!pRemainder->fCurScrambled); Assert(!pDividend->fCurScrambled); Assert(!pDivisor->fCurScrambled);
1407
1408	/*
1409	* Just set both output values to zero as that's the return for several
1410	* special case and the initial state of the general case.
1411	*/
1412	pQuotient->cUsed = 0;
1413	pRemainder->cUsed = 0;
1414
1415	/*
1416	* Dividing something by zero is undefined.
1417	* Diving zero by something is zero, unless the divsor is also zero.
1418	*/
1419	if (!pDivisor->cUsed \|\| !pDividend->cUsed)
1420	return pDivisor->cUsed ? VINF_SUCCESS : VERR_BIGNUM_DIV_BY_ZERO;
1421
1422	/*
1423	* Dividing by one? Quotient = dividend, no remainder.
1424	*/
1425	if (pDivisor->cUsed == 1 && pDivisor->pauElements[0] == 1)
1426	return rtBigNumMagnitudeCopy(pQuotient, pDividend);
1427
1428	/*
1429	* Dividend smaller than the divisor. Zero quotient, all divisor.
1430	*/
1431	int iDiff = rtBigNumMagnitudeCompare(pDividend, pDivisor);
1432	if (iDiff < 0)
1433	return rtBigNumMagnitudeCopy(pRemainder, pDividend);
1434
1435	/*
1436	* Since we already have done the compare, check if the two values are the
1437	* same. The result is 1 and no remainder then.
1438	*/
1439	if (iDiff == 0)
1440	{
1441	int rc = rtBigNumSetUsed(pQuotient, 1);
1442	if (RT_SUCCESS(rc))
1443	pQuotient->pauElements[0] = 1;
1444	return rc;
1445	}
1446
1447	/*
1448	* Do very simple long division. This ain't fast, but it does the trick.
1449	*/
1450	int rc = VINF_SUCCESS;
1451	uint32_t iBit = rtBigNumMagnitudeBitWidth(pDividend);
1452	while (iBit-- > 0)
1453	{
1454	rc = rtBigNumMagnitudeShiftLeftOne(pRemainder, rtBigNumMagnitudeGetBit(pDividend, iBit));
1455	AssertRCBreak(rc);
1456	iDiff = rtBigNumMagnitudeCompare(pRemainder, pDivisor);
1457	if (iDiff >= 0)
1458	{
1459	if (iDiff != 0)
1460	rtBigNumMagnitudeSubThis(pRemainder, pDivisor);
1461	else
1462	pRemainder->cUsed = 0;
1463	rc = rtBigNumMagnitudeSetBit(pQuotient, iBit);
1464	AssertRCBreak(rc);
1465	}
1466	}
1467
1468	/* This shouldn't be necessary. */
1469	rtBigNumStripTrailingZeros(pQuotient);
1470	rtBigNumStripTrailingZeros(pRemainder);
1471	return rc;
1472	}
1473
1474
1475	RTDECL(int) RTBigNumDivide(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
1476	{
1477	Assert(pQuotient != pDividend); Assert(pQuotient != pDivisor); Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor); Assert(pRemainder != pQuotient);
1478	AssertReturn(pQuotient->fSensitive >= (pDividend->fSensitive \| pDivisor->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1479	AssertReturn(pRemainder->fSensitive >= (pDividend->fSensitive \| pDivisor->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1480
1481	int rc = rtBigNumUnscramble(pQuotient);
1482	if (RT_SUCCESS(rc))
1483	{
1484	rc = rtBigNumUnscramble(pRemainder);
1485	if (RT_SUCCESS(rc))
1486	{
1487	rc = rtBigNumUnscramble((PRTBIGNUM)pDividend);
1488	if (RT_SUCCESS(rc))
1489	{
1490	rc = rtBigNumUnscramble((PRTBIGNUM)pDivisor);
1491	if (RT_SUCCESS(rc))
1492	{
1493	/*
1494	* The sign value of the remainder is the same as the dividend.
1495	* The sign values of the quotient follow XOR rules, just like multiplication:
1496	* -3 / 2 = -1; r=-1; 1 ^ 0 = 1
1497	* 3 / -2 = -1; r= 1; 1 ^ 0 = 1
1498	* -3 / -2 = 1; r=-1; 1 ^ 1 = 0
1499	* 3 / 2 = 1; r= 1; 0 ^ 0 = 0
1500	*/
1501	pQuotient->fNegative = pDividend->fNegative ^ pDivisor->fNegative;
1502	pRemainder->fNegative = pDividend->fNegative;
1503
1504	rc = rtBigNumMagnitudeDivide(pQuotient, pRemainder, pDividend, pDivisor);
1505
1506	if (pQuotient->cUsed == 0)
1507	pQuotient->fNegative = 0;
1508	if (pRemainder->cUsed == 0)
1509	pRemainder->fNegative = 0;
1510
1511	rtBigNumScramble((PRTBIGNUM)pDivisor);
1512	}
1513	rtBigNumScramble((PRTBIGNUM)pDividend);
1514	}
1515	rtBigNumScramble(pRemainder);
1516	}
1517	rtBigNumScramble(pQuotient);
1518	}
1519	return rc;
1520	}
1521
1522
1523	/**
1524	* Calculates the modulus of a magnitude value, leaving the sign bit to the
1525	* caller.
1526	*
1527	* All variables must be unscrambled. The sign flag is not considered nor
1528	* touched, this means the caller have to check for zero outputs.
1529	*
1530	* @returns IPRT status code.
1531	* @param pRemainder Where to return the reminder.
1532	* @param pDividend What to divide.
1533	* @param pDivisor What to divide by.
1534	*/
1535	static int rtBigNumMagnitudeModulo(PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
1536	{
1537	Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor);
1538	Assert(!pRemainder->fCurScrambled); Assert(!pDividend->fCurScrambled); Assert(!pDivisor->fCurScrambled);
1539
1540	/*
1541	* Just set the output value to zero as that's the return for several
1542	* special case and the initial state of the general case.
1543	*/
1544	pRemainder->cUsed = 0;
1545
1546	/*
1547	* Dividing something by zero is undefined.
1548	* Diving zero by something is zero, unless the divsor is also zero.
1549	*/
1550	if (!pDivisor->cUsed \|\| !pDividend->cUsed)
1551	return pDivisor->cUsed ? VINF_SUCCESS : VERR_BIGNUM_DIV_BY_ZERO;
1552
1553	/*
1554	* Dividing by one? Quotient = dividend, no remainder.
1555	*/
1556	if (pDivisor->cUsed == 1 && pDivisor->pauElements[0] == 1)
1557	return VINF_SUCCESS;
1558
1559	/*
1560	* Dividend smaller than the divisor. Zero quotient, all divisor.
1561	*/
1562	int iDiff = rtBigNumMagnitudeCompare(pDividend, pDivisor);
1563	if (iDiff < 0)
1564	return rtBigNumMagnitudeCopy(pRemainder, pDividend);
1565
1566	/*
1567	* Since we already have done the compare, check if the two values are the
1568	* same. The result is 1 and no remainder then.
1569	*/
1570	if (iDiff == 0)
1571	return VINF_SUCCESS;
1572
1573	/*
1574	* Do very simple long division. This ain't fast, but it does the trick.
1575	*/
1576	int rc = VINF_SUCCESS;
1577	uint32_t iBit = rtBigNumMagnitudeBitWidth(pDividend);
1578	while (iBit-- > 0)
1579	{
1580	rc = rtBigNumMagnitudeShiftLeftOne(pRemainder, rtBigNumMagnitudeGetBit(pDividend, iBit));
1581	AssertRCBreak(rc);
1582	iDiff = rtBigNumMagnitudeCompare(pRemainder, pDivisor);
1583	if (iDiff >= 0)
1584	{
1585	if (iDiff != 0)
1586	rtBigNumMagnitudeSubThis(pRemainder, pDivisor);
1587	else
1588	pRemainder->cUsed = 0;
1589	AssertRCBreak(rc);
1590	}
1591	}
1592
1593	/* This shouldn't be necessary. */
1594	rtBigNumStripTrailingZeros(pRemainder);
1595	return rc;
1596	}
1597
1598
1599	RTDECL(int) RTBigNumModulo(PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
1600	{
1601	Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor);
1602	AssertReturn(pRemainder->fSensitive >= (pDividend->fSensitive \| pDivisor->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1603
1604	int rc = rtBigNumUnscramble(pRemainder);
1605	if (RT_SUCCESS(rc))
1606	{
1607	rc = rtBigNumUnscramble((PRTBIGNUM)pDividend);
1608	if (RT_SUCCESS(rc))
1609	{
1610	rc = rtBigNumUnscramble((PRTBIGNUM)pDivisor);
1611	if (RT_SUCCESS(rc))
1612	{
1613	/*
1614	* The sign value of the remainder is the same as the dividend.
1615	*/
1616	pRemainder->fNegative = pDividend->fNegative;
1617
1618	rc = rtBigNumMagnitudeModulo(pRemainder, pDividend, pDivisor);
1619
1620	if (pRemainder->cUsed == 0)
1621	pRemainder->fNegative = 0;
1622
1623	rtBigNumScramble((PRTBIGNUM)pDivisor);
1624	}
1625	rtBigNumScramble((PRTBIGNUM)pDividend);
1626	}
1627	rtBigNumScramble(pRemainder);
1628	}
1629	return rc;
1630	}
1631
1632
1633
1634	/**
1635	* Exponentiate the magnitude.
1636	*
1637	* All variables must be unscrambled. The sign flag is not considered nor
1638	* touched, this means the caller have to reject negative exponents.
1639	*
1640	* @returns IPRT status code.
1641	* @param pResult Where to return power.
1642	* @param pBase The base value.
1643	* @param pExponent The exponent (assumed positive or zero).
1644	*/
1645	static int rtBigNumMagnitudeExponentiate(PRTBIGNUM pResult, PCRTBIGNUM pBase, PCRTBIGNUM pExponent)
1646	{
1647	Assert(pResult != pBase); Assert(pResult != pExponent);
1648	Assert(!pResult->fCurScrambled); Assert(!pBase->fCurScrambled); Assert(!pExponent->fCurScrambled);
1649
1650	/*
1651	* A couple of special cases.
1652	*/
1653	int rc;
1654	/* base ^ 0 => 1. */
1655	if (pExponent->cUsed == 0)
1656	{
1657	rc = rtBigNumSetUsed(pResult, 1);
1658	if (RT_SUCCESS(rc))
1659	pResult->pauElements[0] = 1;
1660	return rc;
1661	}
1662
1663	/* base ^ 1 => base. */
1664	if (pExponent->cUsed == 1 && pExponent->pauElements[0] == 1)
1665	return rtBigNumMagnitudeCopy(pResult, pBase);
1666
1667	/*
1668	* Set up.
1669	*/
1670	/* Init temporary power-of-two variable to base. */
1671	RTBIGNUM Pow2;
1672	rc = rtBigNumCloneInternal(&Pow2, pBase);
1673	if (RT_SUCCESS(rc))
1674	{
1675	/* Init result to 1. */
1676	rc = rtBigNumSetUsed(pResult, 1);
1677	if (RT_SUCCESS(rc))
1678	{
1679	pResult->pauElements[0] = 1;
1680
1681	/* Make a temporary variable that we can use for temporary storage of the result. */
1682	RTBIGNUM TmpMultiplicand;
1683	rc = rtBigNumCloneInternal(&TmpMultiplicand, pResult);
1684	if (RT_SUCCESS(rc))
1685	{
1686	/*
1687	* Exponentiation by squaring. Reduces the number of
1688	* multiplications to: NumBitsSet(Exponent) + BitWidth(Exponent).
1689	*/
1690	uint32_t const cExpBits = rtBigNumMagnitudeBitWidth(pExponent);
1691	uint32_t iBit = 0;
1692	for (;;)
1693	{
1694	if (rtBigNumMagnitudeGetBit(pExponent, iBit) != 0)
1695	{
1696	rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, pResult);
1697	if (RT_SUCCESS(rc))
1698	rc = rtBigNumMagnitudeMultiply(pResult, &TmpMultiplicand, &Pow2);
1699	if (RT_FAILURE(rc))
1700	break;
1701	}
1702
1703	/* Done? */
1704	iBit++;
1705	if (iBit >= cExpBits)
1706	break;
1707
1708	/* Not done yet, square the base again. */
1709	rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, &Pow2);
1710	if (RT_SUCCESS(rc))
1711	rc = rtBigNumMagnitudeMultiply(&Pow2, &TmpMultiplicand, &TmpMultiplicand);
1712	if (RT_FAILURE(rc))
1713	break;
1714	}
1715	}
1716	}
1717	RTBigNumDestroy(&Pow2);
1718	}
1719	return rc;
1720	}
1721
1722
1723	RTDECL(int) RTBigNumExponentiate(PRTBIGNUM pResult, PCRTBIGNUM pBase, PCRTBIGNUM pExponent)
1724	{
1725	Assert(pResult != pBase); Assert(pResult != pExponent);
1726	AssertReturn(pResult->fSensitive >= (pBase->fSensitive \| pExponent->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1727
1728	int rc = rtBigNumUnscramble(pResult);
1729	if (RT_SUCCESS(rc))
1730	{
1731	rc = rtBigNumUnscramble((PRTBIGNUM)pBase);
1732	if (RT_SUCCESS(rc))
1733	{
1734	rc = rtBigNumUnscramble((PRTBIGNUM)pExponent);
1735	if (RT_SUCCESS(rc))
1736	{
1737	if (!pExponent->fNegative)
1738	{
1739	pResult->fNegative = pBase->fNegative; /* sign unchanged. */
1740	rc = rtBigNumMagnitudeExponentiate(pResult, pBase, pExponent);
1741	}
1742	else
1743	rc = VERR_BIGNUM_NEGATIVE_EXPONENT;
1744
1745	rtBigNumScramble((PRTBIGNUM)pExponent);
1746	}
1747	rtBigNumScramble((PRTBIGNUM)pBase);
1748	}
1749	rtBigNumScramble(pResult);
1750	}
1751	return rc;
1752	}
1753
1754
1755	/**
1756	* Modular exponentiation, magnitudes only.
1757	*
1758	* All variables must be unscrambled. The sign flag is not considered nor
1759	* touched, this means the caller have to reject negative exponents and do any
1760	* other necessary sign bit fiddling.
1761	*
1762	* @returns IPRT status code.
1763	* @param pResult Where to return the remainder of the power.
1764	* @param pBase The base value.
1765	* @param pExponent The exponent (assumed positive or zero).
1766	* @param pModulus The modulus value (or divisor if you like).
1767	*/
1768	static int rtBigNumMagnitudeModExp(PRTBIGNUM pResult, PRTBIGNUM pBase, PRTBIGNUM pExponent, PRTBIGNUM pModulus)
1769	{
1770	Assert(pResult != pBase); Assert(pResult != pBase); Assert(pResult != pExponent); Assert(pResult != pModulus);
1771	Assert(!pResult->fCurScrambled); Assert(!pBase->fCurScrambled); Assert(!pExponent->fCurScrambled); Assert(!pModulus->fCurScrambled);
1772	int rc;
1773
1774	/*
1775	* Check some special cases to get them out of the way.
1776	*/
1777	/* Div by 0 => invalid. */
1778	if (pModulus->cUsed == 0)
1779	return VERR_BIGNUM_DIV_BY_ZERO;
1780
1781	/* Div by 1 => no remainder. */
1782	if (pModulus->cUsed == 1 && pModulus->pauElements[0] == 1)
1783	{
1784	pResult->cUsed = 0;
1785	return VINF_SUCCESS;
1786	}
1787
1788	/* base ^ 0 => 1. */
1789	if (pExponent->cUsed == 0)
1790	{
1791	rc = rtBigNumSetUsed(pResult, 1);
1792	if (RT_SUCCESS(rc))
1793	pResult->pauElements[0] = 1;
1794	return rc;
1795	}
1796
1797	/* base ^ 1 => base. */
1798	if (pExponent->cUsed == 1 && pExponent->pauElements[0] == 1)
1799	return rtBigNumMagnitudeModulo(pResult, pBase, pModulus);
1800
1801	/*
1802	* Set up.
1803	*/
1804	/* Result = 1; preallocate space for the result while at it. */
1805	rc = rtBigNumSetUsed(pResult, pModulus->cUsed + 1);
1806	if (RT_SUCCESS(rc))
1807	rc = rtBigNumSetUsed(pResult, 1);
1808	if (RT_SUCCESS(rc))
1809	{
1810	pResult->pauElements[0] = 1;
1811
1812	/* ModBase = pBase or pBase % pModulus depending on the difference in size. */
1813	RTBIGNUM Pow2;
1814	if (pBase->cUsed <= pModulus->cUsed + pModulus->cUsed / 2)
1815	rc = rtBigNumCloneInternal(&Pow2, pBase);
1816	else
1817	rc = rtBigNumMagnitudeModulo(rtBigNumInitZeroTemplate(&Pow2, pBase), pBase, pModulus);
1818
1819	/* Need a couple of temporary variables. */
1820	RTBIGNUM TmpMultiplicand;
1821	rtBigNumInitZeroTemplate(&TmpMultiplicand, pResult);
1822
1823	RTBIGNUM TmpProduct;
1824	rtBigNumInitZeroTemplate(&TmpProduct, pResult);
1825
1826	/*
1827	* We combine the exponentiation by squaring with the fact that:
1828	* (ab) mod n = ( (a mod n) (b mod n) ) mod n
1829	*
1830	* Thus, we can reduce the size of intermediate results by mod'ing them
1831	* in each step.
1832	*/
1833	uint32_t const cExpBits = rtBigNumMagnitudeBitWidth(pExponent);
1834	uint32_t iBit = 0;
1835	for (;;)
1836	{
1837	if (rtBigNumMagnitudeGetBit(pExponent, iBit) != 0)
1838	{
1839	rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, pResult);
1840	if (RT_SUCCESS(rc))
1841	rc = rtBigNumMagnitudeMultiply(&TmpProduct, &TmpMultiplicand, &Pow2);
1842	if (RT_SUCCESS(rc))
1843	rc = rtBigNumMagnitudeModulo(pResult, &TmpProduct, pModulus);
1844	if (RT_FAILURE(rc))
1845	break;
1846	}
1847
1848	/* Done? */
1849	iBit++;
1850	if (iBit >= cExpBits)
1851	break;
1852
1853	/* Not done yet, square and mod the base again. */
1854	rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, &Pow2);
1855	if (RT_SUCCESS(rc))
1856	rc = rtBigNumMagnitudeMultiply(&TmpProduct, &TmpMultiplicand, &TmpMultiplicand);
1857	if (RT_SUCCESS(rc))
1858	rc = rtBigNumMagnitudeModulo(&Pow2, &TmpProduct, pModulus);
1859	if (RT_FAILURE(rc))
1860	break;
1861	}
1862
1863	RTBigNumDestroy(&TmpMultiplicand);
1864	RTBigNumDestroy(&TmpProduct);
1865	RTBigNumDestroy(&Pow2);
1866	}
1867	return rc;
1868	}
1869
1870
1871	RTDECL(int) RTBigNumModExp(PRTBIGNUM pResult, PRTBIGNUM pBase, PRTBIGNUM pExponent, PRTBIGNUM pModulus)
1872	{
1873	Assert(pResult != pBase); Assert(pResult != pBase); Assert(pResult != pExponent); Assert(pResult != pModulus);
1874	AssertReturn(pResult->fSensitive >= (pBase->fSensitive \| pExponent->fSensitive \| pModulus->fSensitive),
1875	VERR_BIGNUM_SENSITIVE_INPUT);
1876
1877	int rc = rtBigNumUnscramble(pResult);
1878	if (RT_SUCCESS(rc))
1879	{
1880	rc = rtBigNumUnscramble((PRTBIGNUM)pBase);
1881	if (RT_SUCCESS(rc))
1882	{
1883	rc = rtBigNumUnscramble((PRTBIGNUM)pExponent);
1884	if (RT_SUCCESS(rc))
1885	{
1886	rc = rtBigNumUnscramble((PRTBIGNUM)pModulus);
1887	if (RT_SUCCESS(rc))
1888	{
1889	if (!pExponent->fNegative)
1890	{
1891	pResult->fNegative = pModulus->fNegative; /* pBase ^ pExponent / pModulus; result = remainder. */
1892	rc = rtBigNumMagnitudeModExp(pResult, pBase, pExponent, pModulus);
1893	}
1894	else
1895	rc = VERR_BIGNUM_NEGATIVE_EXPONENT;
1896	rtBigNumScramble((PRTBIGNUM)pModulus);
1897	}
1898	rtBigNumScramble((PRTBIGNUM)pExponent);
1899	}
1900	rtBigNumScramble((PRTBIGNUM)pBase);
1901	}
1902	rtBigNumScramble(pResult);
1903	}
1904	return rc;
1905	}
1906

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/src/VBox/Runtime/common/math/bignum.cpp@ 52018

Download in other formats: