polarathene/answer.md

## answer.md

      
    Raw
  

              answer.md
            
          
    Answer posted to:
https://crypto.stackexchange.com/questions/8687/security-strength-of-rsa-in-relation-with-the-modulus-size
A moderator deleted it about a month later on the basis it wouldn't be useful to anyone due to mostly being a code port.
Making it available to public here in case it'd be useful for anyone else. Running JS or Rust is possibly more easily accessible than the two options in answers provided.

For anyone else curious and wanting to run the math via a language that is more available/accessible (eg a REPL via a web browser), I ported the answer by Charles to Javascript (ES6) below:
const a = 1/3
const b = 2/3
const l = (x) => Math.log(x)
const e = (x) => Math.exp(x)

function to_symmetric_bits(asymmetric_bits) {
  const t = asymmetric_bits * l(2)
  const m = l(t)
  const n = e( l(m) * b )
  const o = e( l(t) * a )
  const p = (1.923 * o * n - 4.69) / l(2)

  return p
}

const sizes = [256, 512, 1024, 2048, 3072, 4096, 7680, 8192, 15360, 16384]

console.log(`RSA Keylength to equivalent 'Bits of Security':`)
sizes.forEach((size) => {
  console.log(`${size} == ${to_symmetric_bits(size)}`)
})

After which, I looked at the official cited NIST source on page 119 and noted that the math while valid seemed not to match the equation... So here's a more direct variant that should be easy to follow when comparing to the linked equation:
function to_symmetric_bits(keylength) {
  const a = keylength * Math.log(2) // L * ln(2)
  const b = Math.pow(Math.log(a), 2) // ln(L * ln(2))^2

  // Top half (numerator) / ln(2) == x
  const numerator = 1.923 * Math.cbrt(a) * Math.cbrt(b) - 4.69
  const x = numerator / Math.log(2)

  return x
}

const sizes = [256, 512, 1024, 2048, 3072, 4096, 7680, 8192, 15360, 16384]

console.log(`RSA Keylength to equivalent 'Bits of Security':`)
sizes.forEach((size) => {
  console.log(`${size} == ${to_symmetric_bits(size)}`)
})

Output:
RSA Keylength to equivalent 'Bits of Security':
256 == 39.8983534444018
512 == 57.16312330388321
1024 == 79.99990535893299
2048 == 110.11760837749868
3072 == 131.97008244496166
4096 == 149.73076030163335
7680 == 196.25255668822675
8192 == 201.70630874279217
15360 == 262.6186131379134
16384 == 269.7522498627511


The document on page 119 also cites after the equation:

If the lengths of the Diffie-Hellman public and private keys are L and N, correspondingly, then the length y of a symmetric key of approximately the same strength can be computed as:
y = min(x, N / 2)
where x is computed as in formula (1) above

N values are shared for some key lengths at the top of page 119, when divided by 2, you end up with the 112, 128, 192, 256 values. Which for the output shared above would result in 110(2048), 128(3072), 192(7680), 256(15360).
The document referenced has an initial release date of 2003, and was last updated in 2020. The equation doesn't appear to have changed from what has been shown in this thread from answers years ago however.

I didn't notice originally, but Charles initially ported the GNFS algorithm from Reid, and for whatever reason later modified it to adjust to the NIST algorithm. That is there shouldn't have been any a, b fractions or Math.exp()? The GNFS equation also has Math.cbrt(64/9) which is where the 1.923 value came from.
The following is JS equivalent, but you won't have success with it due to JS numbers being larger than supported (infinity starts from 2^1024):
// log2(exp(cbrt(64/9) * log(2^1024)^(1/3) * log(log(2^1024))^(2/3)))
function to_symmetric_bits(keylength) {
  const n = Math.pow(2, keylength)

  const a = Math.cbrt(64/9)
  const b = Math.pow(Math.log(n),1/3)
  const c = Math.pow(Math.log(Math.log(n)), 2/3)

  const x = Math.log2(Math.exp(a * b * c))

  return x
}

Turns out t var from Charles approach produces the same desired output for the n value in my code above. This avoids the ridiculously large number becoming infinity (which would affect most languages float numbers? Not just JS, I verified with Rust f64 type):
function to_symmetric_bits(keylength) {
  const n = keylength * Math.log(2)
 
  const a = Math.cbrt(64/9)
  const b = Math.pow(n, 1/3)
  const c = Math.pow(Math.log(n), 2/3)

  const x = Math.log2(Math.exp(a * b * c))

  return x
}
Rust:
fn main() {
    let sizes: Vec<i32> = vec![256, 512, 1024, 2048, 3072, 4096, 7680, 8192];
    
    println!("RSA Keylength to equivalent 'Bits of Security':");
    for size in sizes.into_iter() {
        println!("{} == {}", size, to_symmetric_bits(size as f64));
    }
}

fn to_symmetric_bits(keylength: f64) -> f64 {
    let n = (2_f64).ln() * keylength;

    let a = f64::cbrt(64.0/9.0);
    let b = n.powf(1.0/3.0);
    let c = n.ln().powf(2.0/3.0);

    let x = ((a * b * c).exp()).log2();

    x
}
For anyone interested of the output for 256-bit and 512-bit RSA:
256 == 46.664579283290124
512 == 63.92934399904213