6ebd5502c7c396573275d0817d2a705b cryptography_a2018v2p23.pdf 9f48cbf84ba4720f4ebeab79df46bca152e509bc cryptography_a2018v2p23.pdf b07b8a919d8203f23805a3a601746ef204e24f7cdca4ce3d4cc0bb6c535de477 cryptography_a2018v2p23.pdf Title: A Secure Algorithm for Inversion Modulo 2k Subject: Modular inversions are widely employed in public key crypto-systems, and it is known that they imply a bottleneck due to the expensive computation. Recently, a new algorithm for inversions modulo pk was proposed, which may speed up the calculation of a modulus dependent quantity used in the Montgomery multiplication. The original algorithm lacks security countermeasures; thus, a straightforward implementation may expose the input. This is an issue if that input is a secret. In the RSA-CRT signature using Montgomery multiplication, the moduli are secrets (primes p and q). Therefore, the moduli dependent quantities related to p and q must be securely computed. This paper presents a security analysis of the novel method considering that it might be used to compute secrets. We demonstrate that a Side Channel Analysis leads to disclose the data being manipulated. In consequence, a secure variant for inversions modulo 2k is proposed, through the application of two known countermeasures. In terms of performance, the secure variant is still comparable with the original one. Keywords: modular inversion; montgomery multiplication; RSA; side channel attack Author: Sadiel de la Fe and Carles Ferrer Creator: LaTeX with hyperref package Producer: pdfTeX-1.40.17 CreationDate: Thu Sep 13 11:16:19 2018 CEST ModDate: Thu Sep 13 11:16:19 2018 CEST Tagged: no UserProperties: no Suspects: no Form: none JavaScript: no Pages: 8 Encrypted: no Page size: 595.276 x 841.89 pts (A4) Page rot: 0 File size: 228736 bytes Optimized: no PDF version: 1.5 name type encoding emb sub uni object ID ------------------------------------ ----------------- ---------------- --- --- --- --------- OQCNNS+URWPalladioL-Ital Type 1 Custom yes yes no 71 0 KXPHDO+URWPalladioL-Bold Type 1 Custom yes yes no 72 0 TAHCEI+URWPalladioL-BoldItal Type 1 Custom yes yes no 73 0 OXBKYU+TeXGyreAdventor-Bold Type 1 Custom yes yes no 74 0 UXHGWK+URWPalladioL-Roma Type 1 Custom yes yes no 75 0 MCBCCI+SourceSansRoman-Regular Type 1C Custom yes yes no 86 0 MCBCCM+SourceSansRoman.613wght Type 1C Custom yes yes no 87 0 MCBCCO+SourceSansRoman-Bold Type 1C Custom yes yes no 88 0 SOSTRQ+CMR10 Type 1 Builtin yes yes no 119 0 ZKZTOL+CMSY10 Type 1 Builtin yes yes no 120 0 RLYTRW+CMMI10 Type 1 Builtin yes yes no 126 0 WEIJUK+CMSY9 Type 1 Builtin yes yes no 236 0 Jhove (Rel. 1.22.1, 2019-04-17) Date: 2020-01-21 05:40:18 CET RepresentationInformation: cryptography_a2018v2p23.pdf ReportingModule: PDF-hul, Rel. 1.12.1 (2019-04-17) LastModified: 2020-01-20 10:46:05 CET Size: 228736 Format: PDF Version: 1.5 Status: Well-Formed and valid SignatureMatches: PDF-hul MIMEtype: application/pdf PDFMetadata: Objects: 0 FreeObjects: 1 IncrementalUpdates: 0 DocumentCatalog: ViewerPreferences: HideToolbar: false HideMenubar: false HideWindowUI: false FitWindow: true CenterWindow: false DisplayDocTitle: false NonFullScreenPageMode: UseNone Direction: L2R ViewArea: CropBox ViewClip: CropBox PrintArea: CropBox PageClip: CropBox PageLayout: SinglePage PageMode: UseNone Outlines: Item: Title: ぉのぴひはつふっぴどはの Children: Item: Title: げこぁ〭ぃげごぜ〴ぜ〰ぷどぴとぜ〴ぜ〰きはのぴではねづひべぜ〴ぜ〰きふぬぴどばぬどっちぴどはのび Item: Title: くふひぜ〴ぜ〰ぃはのぴひどぢふぴどはのび Item: Title: ぐちばづひぜ〴ぜ〰くひでちのどぺちぴどはの Item: Title: くのぜ〴ぜ〰ちぜ〴ぜ〰ぎづぷぜ〴ぜ〰ぁぬではひどぴとねぜ〴ぜ〰てはひぜ〴ぜ〰ぉのぶづひびどはのぜ〴ぜ〰きはつふぬはぜ〴ぜ〰ばに Item: Title: こづっふひどぴべぜ〴ぜ〰ぁのちぬべびどびぜ〴ぜ〰てはひぜ〴ぜ〰ば〽〲 Children: Item: Title: ぁびべねねづぴひどっぜ〴ぜ〰ぉぴづひちぴどはのび Item: Title: くばづひちぴどはのびぜ〴ぜ〰がちぴづのっべ Item: Title: ぁぜ〴ぜ〰こづっふひづぜ〴ぜ〰きづぴとはつぜ〴ぜ〰てはひぜ〴ぜ〰ぉのぶづひびどはのぜ〴ぜ〰きはつふぬはぜ〴ぜ〰〲に Item: Title: ぃはのっぬふびどはのび Item: Title: げづてづひづのっづび Filters: FilterPipeline: FlateDecode Images: Image: NisoImageMetadata: FormatName: image/png ImageWidth: 568 ImageHeight: 142 ColorSpace: RGB BitsPerSample: 8 BitsPerSampleUnit: integer Filter: FlateDecode Fonts: Type1: Font: BaseFont: OQCNNS+URWPalladioL-Ital FontSubset: true FirstChar: 39 LastChar: 151 FontDescriptor: FontName: OQCNNS+URWPalladioL-Ital Flags: Symbolic FontBBox: -170, -305, 1010, 941 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: SOSTRQ+CMR10 FontSubset: true FirstChar: 40 LastChar: 93 FontDescriptor: FontName: SOSTRQ+CMR10 Flags: Symbolic FontBBox: -40, -250, 1009, 750 FontFile: true Font: BaseFont: KXPHDO+URWPalladioL-Bold FontSubset: true FirstChar: 3 LastChar: 134 FontDescriptor: FontName: KXPHDO+URWPalladioL-Bold Flags: Symbolic FontBBox: -152, -301, 1000, 935 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: ZKZTOL+CMSY10 FontSubset: true FirstChar: 0 LastChar: 50 FontDescriptor: FontName: ZKZTOL+CMSY10 Flags: Symbolic FontBBox: -29, -960, 1116, 775 FontFile: true Font: BaseFont: TAHCEI+URWPalladioL-BoldItal FontSubset: true FirstChar: 107 LastChar: 112 FontDescriptor: FontName: TAHCEI+URWPalladioL-BoldItal Flags: Symbolic FontBBox: -170, -300, 1073, 935 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: OXBKYU+TeXGyreAdventor-Bold FontSubset: true FirstChar: 68 LastChar: 73 FontDescriptor: FontName: OXBKYU+TeXGyreAdventor-Bold Flags: Symbolic FontBBox: -679, -304, 1661, 1236 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: UXHGWK+URWPalladioL-Roma FontSubset: true FirstChar: 2 LastChar: 242 FontDescriptor: FontName: UXHGWK+URWPalladioL-Roma Flags: Symbolic FontBBox: -166, -283, 1021, 943 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: WEIJUK+CMSY9 FontSubset: true FirstChar: 13 LastChar: 13 FontDescriptor: FontName: WEIJUK+CMSY9 Flags: Symbolic FontBBox: -29, -958, 1146, 777 FontFile: true Font: BaseFont: RLYTRW+CMMI10 FontSubset: true FirstChar: 60 LastChar: 60 FontDescriptor: FontName: RLYTRW+CMMI10 Flags: Symbolic FontBBox: -32, -250, 1048, 750 FontFile: true Pages: Page: Sequence: 1 Annotations: Annotation: Subtype: Link Rect: 75, 757, 213, 793 Annotation: Subtype: Link Rect: 474, 757, 519, 793 Annotation: Subtype: Link Rect: 166, 682, 179, 694 Annotation: Subtype: Link Rect: 467, 586, 519, 608 Annotation: Subtype: Link Rect: 179, 226, 186, 235 ActionDest: 217 Annotation: Subtype: Link Rect: 188, 213, 195, 221 ActionDest: 217 Annotation: Subtype: Link Rect: 195, 212, 202, 221 ActionDest: 217 Annotation: Subtype: Link Rect: 176, 186, 183, 194 ActionDest: 232 Annotation: Subtype: Link Rect: 301, 145, 308, 154 ActionDest: 232 Annotation: Subtype: Link Rect: 501, 91, 508, 100 ActionDest: 232 Annotation: Subtype: Link Rect: 508, 91, 515, 100 ActionDest: 232 Annotation: Subtype: Link Rect: 175, 38, 284, 50 Annotation: Subtype: Link Rect: 377, 38, 519, 50 Page: Sequence: 2 Annotations: Annotation: Subtype: Link Rect: 365, 743, 372, 751 ActionDest: 232 Annotation: Subtype: Link Rect: 427, 673, 434, 682 ActionDest: 232 Annotation: Subtype: Link Rect: 437, 659, 444, 668 ActionDest: 232 Annotation: Subtype: Link Rect: 488, 646, 500, 655 ActionDest: 232 Annotation: Subtype: Link Rect: 503, 646, 515, 655 ActionDest: 232 Annotation: Subtype: Link Rect: 161, 458, 168, 470 ActionDest: 115 Annotation: Subtype: Link Rect: 197, 458, 204, 470 ActionDest: 115 Annotation: Subtype: Link Rect: 424, 382, 431, 394 ActionDest: 115 Annotation: Subtype: Link Rect: 345, 192, 352, 206 ActionDest: 115 Page: Sequence: 3 Annotations: Annotation: Subtype: Link Rect: 303, 546, 310, 558 ActionDest: 49 Annotation: Subtype: Link Rect: 512, 546, 519, 558 ActionDest: 150 Annotation: Subtype: Link Rect: 313, 533, 320, 545 ActionDest: 167 Annotation: Subtype: Link Rect: 421, 520, 428, 533 ActionDest: 195 Annotation: Subtype: Link Rect: 226, 451, 233, 460 ActionDest: 232 Annotation: Subtype: Link Rect: 135, 326, 142, 338 ActionDest: 150 Annotation: Subtype: Link Rect: 401, 329, 408, 338 ActionDest: 232 Annotation: Subtype: Link Rect: 456, 120, 463, 132 ActionDest: 115 Annotation: Subtype: Link Rect: 492, 120, 500, 132 ActionDest: 115 Page: Sequence: 4 Annotations: Annotation: Subtype: Link Rect: 149, 740, 156, 754 ActionDest: 150 Annotation: Subtype: Link Rect: 175, 699, 182, 711 ActionDest: 167 Annotation: Subtype: Link Rect: 503, 496, 515, 505 ActionDest: 232 Annotation: Subtype: Link Rect: 219, 305, 231, 314 ActionDest: 232 Annotation: Subtype: Link Rect: 208, 248, 215, 260 ActionDest: 167 Page: Sequence: 5 Annotations: Annotation: Subtype: Link Rect: 172, 359, 179, 371 ActionDest: 167 Annotation: Subtype: Link Rect: 276, 208, 283, 220 ActionDest: 187 Annotation: Subtype: Link Rect: 508, 208, 515, 220 ActionDest: 187 Annotation: Subtype: Link Rect: 278, 195, 285, 207 ActionDest: 187 Annotation: Subtype: Link Rect: 321, 100, 328, 112 ActionDest: 150 Page: Sequence: 6 Annotations: Annotation: Subtype: Link Rect: 459, 720, 466, 732 ActionDest: 167 Annotation: Subtype: Link Rect: 175, 707, 182, 719 ActionDest: 195 Annotation: Subtype: Link Rect: 365, 357, 379, 369 ActionDest: 187 Annotation: Subtype: Link Rect: 478, 168, 486, 180 ActionDest: 217 Page: Sequence: 7 Annotations: Annotation: Subtype: Link Rect: 460, 473, 467, 487 ActionDest: 217 Annotation: Subtype: Link Rect: 480, 153, 516, 164 Annotation: Subtype: Link Rect: 318, 89, 356, 100 Page: Sequence: 8 Annotations: Annotation: Subtype: Link Rect: 97, 727, 246, 738 Annotation: Subtype: Link Rect: 480, 714, 516, 725 Annotation: Subtype: Link Rect: 100, 663, 137, 674 Annotation: Subtype: Link Rect: 296, 637, 334, 648 Annotation: Subtype: Link Rect: 249, 611, 354, 622 Annotation: Subtype: Link Rect: 97, 585, 198, 596 Annotation: Subtype: Link Rect: 396, 559, 434, 570 Annotation: Subtype: Link Rect: 136, 470, 173, 480 Annotation: Subtype: Link Rect: 76, 428, 166, 459 Annotation: Subtype: Link Rect: 234, 422, 424, 433 Checksum: ef286a6c Type: CRC32 Checksum: 6ebd5502c7c396573275d0817d2a705b Type: MD5 Checksum: 9f48cbf84ba4720f4ebeab79df46bca152e509bc Type: SHA-1