# High Level Design of RSA acceleration with OpenCL

## Available inputs
- `m`:  message                   | `+0x69B9AA2D1F117E07,A22E4842F11D8379`
- `c`:  cipher                    | `+0x6067F21E9D596CBB,F189A8E45CB9DD45`
- `p`:  prime1                    | `+0xFAE3198C51595103`
- `q`:  prime2                    | `+0xC8BCF55B5A50C9A1`
- `n`:  `p*q`                     | `+0xC4BA9B314149E72A,A3D0BA93A8B74DE3`
- `e`:  public exponent           | `+0x10001`
- `d`:  private exponent          | `+0x96049703E07DB2C1,F51C7472EBF601`
- `dp`: `d % p-1`                 | `+0xAECF4E1DD710C4C1`
- `dq`: `d % q-1`                 | `+0x99B720C7709496A1`
- `qi`: `q` inverse in modulo `p` | `+0xDE76068BE05353DD`

## Computed inputs on cpu
- `pb`:  `2^NoOfBits(c)/p`        | `+0x1,053793198EEC23FD`
- `qb`:  `2^NoOfBits(c)/q`        | `+0x1,4679A0FE8C41C19A`
- `rn`:  `2^kn` ∋ `kn` is number of bits in `n`
                                  | `+0x1,0000000000000000,0000000000000000`
- `r2n`: `(rn^2)%n`               | `+0x1BCEC6F26C351037,3051DCF202490CF9`
- `rni,
  -np`:  `ExtendedEuclideanFunction(r2n, n, &rni, &np)`
                                  | `-0x4E55A01C12C364EA,99723D42A5A00C90,
                                     +0x65EF70C73E8C69B4,47547B7828AA5FCB`
- `rp`:  `2^kp` ∋ `kp` is number of bits in `p` 
                                  | `+0x1,0000000000000000`
- `r2p`: `(rp^2)%p`               | `+0xECB465A30BE38709`
- `rpi,
  -pp`:  `ExtendedEuclideanFunction(r2p, p, &rpi, &pp)`
                                  | `-0x75D62A08B4906CAB, +0x783CED93A5CCA1AB`
- `rq`:  `2^kq` ∋ `kq` is number of bits in `q`
                                  | `+0x1,0000000000000000`
- `r2q`: `(rq^2)%q`               | `+0x1A7EBD6F85835426`
- `rqi,
  -qp`:  `ExtendedEuclideanFunction(r2p, p, &rpi, &pp)`
                                  | `+0x561325AEE519FA8D, -0x6DC5472B151EA59F`

## Encryption
- Outputs cipher **c**.
```
c = m^e%n
  = MontgomeryExponentiation(m, e, n, rn, r2n, np) {
       mb = MontgomeryReduction(m, r2n, n, rn, np) {
          T = m * r2n;
          M = (T * np)%rn
          U = (T + M*n)/rn
          if (U>=m)
             return U - m
          else
             return U
       }
       r2nb = MontgomeryReduction(1, r2n, n, rn, np)
       cb = (0thBit(e)==1) ? MontgomeryReduction(mb, r2nb, n, rn, np) : 1
       for i = 1 upto MSBPosition(e) do {
          mb = MontgomeryReduction(mb, mb, n, rn, np)
          if (iThBit(e)==1) {
             mb = MontgomeryReduction(cb, mb, n, rn, np)
          }
       }
       c = MontgomeryReduction(mb, 1, n, rn, np)
       return c
    }
```
- Use 
https://www.boxentriq.com/code-breaking/big-number-calculator and
https://www.boxentriq.com/code-breaking/modular-exponentiation to validate the
output of a function.

## Decryption
- Outputs message **m**.
```
m = c^d%n 
  = ChineseRamainder(c, dp, dq, p, q, qInv, pb, r2p, rp, pp, qb, r2q, rq, qp) {
       cp = c%p
          = Barrett(c, p, pb) {
               v1 = c % NoOfBitsInAWord^(NoOfWordsInP+1)
               q1 = c/(NoOfBitsInaWord^(NoOfWordsInP−1))
               q2 = q1·pb
               q3 = q2/(NoOfBitsInaWord^(NoOfWordsInP+1))
               v2 = (q3 · c) % NoOfBitsInWord^(NoOfWordsInP+1)
               v = v1 − v2
               if (v < 0)
                  v = v + NoOfBitsInaWord^(NoOfWordsInP+1)
               while (v ≥ p)
                  v = v − p
               end while
               return v
            }
       mp = MontgomeryExponentiation(dp, cp, p, rp, r2p, pp)
       cq = c%q = Barrett(c, q, qb)
       mq = MontgomeryExponentiation(dq, cq, q, rq, r2q, qp)
       return (mq + q*Barrett((mp-mq)*qi, p, pb))
    }
```

## variable sharing functions
- Barrett, montgomeryExp(montRed)
- mul, add
- montred