Bug 1153

Summary: 2048-bit RSA demo using SVP64 and bigint insns
Product: Libre-SOC's second ASIC Reporter: Jacob Lifshay <programmerjake>
Component: source codeAssignee: Jacob Lifshay <programmerjake>
Status: RESOLVED DUPLICATE    
Severity: enhancement CC: libre-soc-bugs, programmerjake
Priority: ---    
Version: unspecified   
Hardware: PC   
OS: Linux   
See Also: https://bugs.libre-soc.org/show_bug.cgi?id=942
NLnet milestone: NLnet.2021.02A.052.CryptoRouter total budget (EUR) for completion of task and all subtasks: 0
budget (EUR) for this task, excluding subtasks' budget: 0 parent task for budget allocation: 773
child tasks for budget allocation: The table of payments (in EUR) for this task; TOML format:
Bug Depends on:    
Bug Blocks: 773    

Description Jacob Lifshay 2023-09-08 03:08:07 BST
(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 250 lines of tests
  * extra tests for sub-parts of the algorithm due to its complexity
  * rounding to EUR 1500
* 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
Comment 1 Jacob Lifshay 2023-09-08 03:11:28 BST
adjusting divmod tests estimate down
Comment 2 Jacob Lifshay 2023-09-08 04:06:47 BST

*** This bug has been marked as a duplicate of bug 1044 ***