Bug 1153 - 2048-bit RSA demo using SVP64 and bigint insns
Summary: 2048-bit RSA demo using SVP64 and bigint insns
Status: RESOLVED DUPLICATE of bug 1044
Alias: None
Product: Libre-SOC's second ASIC
Classification: Unclassified
Component: source code (show other bugs)
Version: unspecified
Hardware: PC Linux
: --- enhancement
Assignee: Jacob Lifshay
Depends on:
Blocks: 773
  Show dependency treegraph
Reported: 2023-09-08 03:08 BST by Jacob Lifshay
Modified: 2023-09-08 04:06 BST (History)
2 users (show)

See Also:
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:


Note You need to log in before you can comment on or make changes to this bug.
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 ***