# zbMATH — the first resource for mathematics

Double-speed Barrett moduli. (English) Zbl 1405.94065
Ryan, Peter Y. A. (ed.) et al., The new codebreakers. Essays dedicated to David Kahn on the occasion of his 85th birthday. Berlin: Springer (ISBN 978-3-662-49300-7/pbk; 978-3-662-49301-4/ebook). Lecture Notes in Computer Science 9100, 148-158 (2016).
Summary: Modular multiplication and modular reduction are the atomic constituents of most public-key cryptosystems. Amongst the numerous algorithms for performing these operations, a particularly elegant method was proposed by Barrett. This method builds the operation $$a \bmod b$$ from bit shifts, multiplications and additions in $$\mathbb Z$$. This allows to build modular reduction at very marginal code or silicon costs by leveraging existing hardware or software multipliers.
This paper presents a method allowing to double the speed of Barrett’s algorithm by using specific composite moduli. This is particularly useful for lightweight devices where such an optimization can make a difference in terms of power consumption, cost and processing time. The generation of composite moduli with a predetermined portion is a well-known technique and the use of such moduli is considered, in statu scientiæ, as safe as using randomly generated composite moduli.
For the entire collection see [Zbl 1334.94030].

##### MSC:
 94A60 Cryptography
Full Text:
##### References:
 [1] Barrett, P.: Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 311–323. Springer, Heidelberg (1987) [2] Bernstein, R.: Multiplication by integer constants. Softw. Pract. Exp. 16(7), 641–652 (1986) · doi:10.1002/spe.4380160704 [3] Bosselaers, A., Govaerts, R., Vandewalle, J.: Comparison of three modular reduction functions. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 175–186. Springer, Heidelberg (1994) · Zbl 0871.94026 · doi:10.1007/3-540-48329-2_16 [4] Brickell, E.F.: A Fast Modular Multiplication Algorithm with Applications to TwoKey Cryptography. Crypto 1982, pp. 51–60. Springer, New York (1983) [5] Douguet, M., Dupaquis, V.: Modular reduction using a special form of the modulus. U.S. Patent Application 12/033,512, filed February 19, Atmel Corporation (2008) [6] Joye, M.: RSA moduli with a predetermined portion: techniques and applications. In: Chen, L., Mu, Y., Susilo, W. (eds.) ISPEC 2008. LNCS, vol. 4991, pp. 116–130. Springer, Heidelberg (2008) · Zbl 1300.94061 · doi:10.1007/978-3-540-79104-1_9 [7] Knežević, M., Batina, L., Verbauwhede, I.: Modular reduction without precomputational phase. In: Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS), pp. 1389–1392. IEEE (2009) [8] Knobloch, H.-J.: A smart card implementation of the Fiat-Shamir identification scheme. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 87–95. Springer, Heidelberg (1988) · doi:10.1007/3-540-45961-8_8 [9] Knuth, D.E.: The Art of Computer Programming. Seminumerical Algorithms, vol. 2, 2nd edn. Addison Wesley, Reading (1981) · Zbl 0477.65002 [10] Lenstra, A.K.: Generating RSA moduli with a predetermined portion. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 1–10. Springer, Heidelberg (1998) · Zbl 0930.94023 · doi:10.1007/3-540-49649-1_1 [11] Meister, G.: On an implementation of the Mohan-Adiga algorithm. In: Damgård, I.B. (ed.) EUROCRYPT 1990. LNCS, vol. 473, pp. 496–500. Springer, Heidelberg (1991) · Zbl 0825.94190 · doi:10.1007/3-540-46877-3_48 [12] Montgomery, P.L.: Modular multiplication without trial division. Math. Comput. 44(170), 519–521 (1985) · Zbl 0559.10006 · doi:10.1090/S0025-5718-1985-0777282-X [13] National Institute of Standards and Technology (NIST): Digital Signature Standard. FIPS PUB 186–2 (2013) [14] National Institute of Standards and Technology (NIST): Digital Signature Standard. FIPS PUB 186–4 (2013) [15] Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key cryptosystems. Commun. Assoc. Comput. Mach. 21(2), 120–126 (1978) · Zbl 0368.94005 [16] Shparlinski, I.E.: On RSA moduli with prescribed bit patterns. Des. Codes Cryptogr. 39(1), 113–122 (2006) · Zbl 1172.11047 · doi:10.1007/s10623-005-3137-2 [17] Vanstone, S.A., Zuccherato, R.J.: Short RSA keys and their generation. J. Cryptol. 8(2), 101–114 (1995) · Zbl 0828.94010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.