[Libre-soc-bugs] [Bug 1153] New: 2048-bit RSA demo using SVP64 and bigint insns

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=1153

            Bug ID: 1153
           Summary: 2048-bit RSA demo using SVP64 and bigint insns
           Product: Libre-SOC's second ASIC
           Version: unspecified
          Hardware: PC
                OS: Linux
            Status: CONFIRMED
          Severity: enhancement
          Priority: ---
         Component: source code
          Assignee: programmerjake at gmail.com
          Reporter: programmerjake at gmail.com
                CC: libre-soc-bugs at lists.libre-soc.org,
                    programmerjake at gmail.com
            Blocks: 773
   NLnet milestone: NLnet.2021.02A.052.CryptoRouter
    parent task for 773
 budget allocation:

(previous attempt at much faster algorithms that ended up stuck in the
register-allocator rabbit-hole: bug #942)

this task is to demonstrate 2048-bit RSA (just the modular exponentiation
algorithm, not key generation or padding or any other parts) but using very
simple algorithms (basic O(n^2) multiplication using bigint insns and basic
O(n^2) division)

no attempt at constant-time is to be made.

I picked 2048-bit because that's the smallest commonly used size and the
4096-bit intermediate value barely fits in SimpleV's 128 integer registers,
taking up 64x64-bit registers when leaving space for other temporaries and
stuff.

Using budget estimation factor of 2.70 EUR per line of code from bug #1025

* TODO: basic 2048-bit * 2048-bit -> 4096-bit O(n^2) unsigned multiplication
  * REMAP-based multiplication algorithm will be a separate task
  * estimating 200 lines of code and 150 lines of tests
  * rounding to EUR 900
* TODO: basic O(n^2) unsigned divmod using Knuth's Algorithm D
  4096-bit by 2048-bit division with 2048-bit remainder
  * estimating 300 lines of code and 300 lines of tests
  * extra tests for sub-parts of the algorithm due to its complexity
  * rounding to EUR 1600
* TODO: basic modular exponentiation algorithm
  calls the mul and divmod algorithms
  * estimating 100 lines of code and 100 lines of tests
  * rounding to EUR 500


Referenced Bugs:

https://bugs.libre-soc.org/show_bug.cgi?id=773
[Bug 773] High-Level Demos of Cryptographic and Other Relevant Algorithms
-- 
You are receiving this mail because:
You are on the CC list for the bug.