[US Patent & Trademark Office, Patent Full Text and Image Database] [Home] [Boolean Search] [Manual Search] [Number Search] [Help] [PREV_LIST] [HIT_LIST] [NEXT_LIST] [PREV_DOC] [NEXT_DOC] [Bottom] [View Shopping Cart] [Add to Shopping Cart] [Image] ( 1726 of 5545 ) ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ United States Patent 8,218,760 Joye July 10, 2012 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Method and a device for generating compressed RSA moduli Abstract Method and device for generating factors of a RSA modulus N with a predetermined portion N.sub.h, the RSA modulus comprising at least two factors. A first prime p is generated; a value N.sub.h that forms a part of modulus N is obtained; a second prime q is generated in an interval dependent from p and N.sub.h so that pq is a RSA modulus that shares N.sub.h; and information enabling the calculation of the modulus/V is outputted. ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Inventors: Joye; Marc (Cesson-Sevigne, FR) Assignee: Thomson Licensing (Boulogne, Billancourt, FR) Appl. No.: 12/449,654 Filed: February 19, 2008 PCT Filed: February 19, 2008 PCT No.: PCT/EP2008/052017 371(c)(1),(2), August 19, 2009 (4) Date: PCT Pub. No.: WO2008/104482 PCT Pub. Date: September 04, 2008 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Foreign Application Priority Data ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Feb 27, 2007 [EP] 07300830 Current U.S. Class: 380/30 ; 380/28; 380/44; 380/45; 380/46; 380/47; 708/250; 708/251; 708/252; 708/253; 708/254; 708/255; 708/256 Current International Class: H04L 29/06 (20060101) Field of Search: 380/44-30 708/250-256 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ References Cited [Referenced By] ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ U.S. Patent Documents 6134325 October 2000 Vanstone et al. 6928163 August 2005 Matyas et al. 2002/0154768 October 2002 Lenstra 2003/0021410 January 2003 Miyazaki et al. 2004/0049526 March 2004 Joye et al. 2004/0114757 June 2004 Joye et al. 2004/0264702 December 2004 Eastlake, III Other References What is Lossless Compression? Publisher: wiseGeek; Date: Dec. 25, 2004. cited by examiner . Encryption by SearchSecurity.com; Date: Jul. 31, 2000. cited by examiner . Short RSA Keys and Their Generation by Vanstone et al; Publisher: International Association for Cryptologic Research; Date: Jan. 4, 1994. cited by examiner . A.K. Lenstra: "Generating RSA moduli with a predetermined portion" Lecture Notes in Computer Science, Springer Erlag, Berlin, DE, No. 1514, Oct. 1, 1998, pp. 1-10 XP002108059. cited by other . Marc Joye et al: "Fast Generation of Prime Numbers on Portable Devices: An Update" Cryptographic Hardware and Embedded Systems-CHES 2008, Lecture Notes in Computer Science , Springer, Berlin, DE, vol. 4249, Jan. 1, 2006, pp. 160-173, XP019046817. cited by other . Search Report Dated Sep. 30, 2008. cited by other. Primary Examiner: Arani; Taghi Assistant Examiner: Herzog; Madhuri Attorney, Agent or Firm: Carter; Jeffrey D. ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Claims ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ The invention claimed is: 1. A method of generating factors of a RSA modulus N with a predetermined portion N.sub.h and a non-predetermined portion N.sub.l, the RSA modulus N comprising at least two factors, the method being performed by a device and comprising steps of: generating a first prime p; obtaining a value N.sub.h that forms a part of the RSA modulus N; generating a second prime q; and outputting at least a lossless compressed representation of the RSA modulus N that enables unambiguous recovery of the RSA modulus N; wherein the second prime q is randomly generated in a predetermined interval dependent from p and N.sub.h so that pq is a RSA modulus that shares N.sub.h; wherein the predetermined portion N.sub.h heads the RSA modulus N; wherein the RSA modulus N is a n-bit modulus and the predetermined portion N.sub.h comprises k bits; wherein the first prime p is generated in an interval p.epsilon. [2.sup.n-n.sup.0.sup.-1/2,2.sup.n-n.sup.0-1] so that gcd(p-1,e)=1, wherein e is a public exponent and wherein 1