forge icon indicating copy to clipboard operation
forge copied to clipboard

Collision on deterministic RSA keys with different seed

Open fai516 opened this issue 3 years ago • 0 comments

I ran an experiment on forge.pki.rsa.generateKeyPair method with input 4096 bits and different seed A a996dc4726424c0e368c898da1a77dba58596340ae3dd222f39ec4625eb1a960 and B a9a6b63507dc2dedfac4afa8a2074c1d58fa97cc04901e9844ab937212567fa5

code example: https://replit.com/@YikFaiFai1/node-forge#index.js

it turns out that both p and q are identical

seed:  a996dc4726424c0e368c898da1a77dba58596340ae3dd222f39ec4625eb1a960
p:  BigInteger {
  data: [
    204819291, 125184622,  55213757,  41384530,  56329195,
    161802729, 237398828, 171976160, 242659852,  54680845,
      6379184, 128013249, 244497257,  18176204, 189753025,
     39047408, 239706085,  26783302,   7346839, 119806554,
    118802474,   3786056,  13456447, 173445427, 256995741,
    189070187,  63112685, 260143701, 191598716, 109140013,
     68189659,  30773098,  63978869,  89149752,   4307920,
    215590892,   3869222, 139890016,  64084517, 229392706,
    202435813, 129101180, 179767410, 244014137, 198460685,
    105485896,  72299551, 120998475,  78936425, 266471636,
    185225152, 189097146,   7723396,  34539926, 251950413,
     30479482,  34301206, 265663729, 118857769,  12785570,
     74972162, 160664107, 155496914, 179985101, 156964582,
     46179109, 122606868,  88861884, 244933372,  60989407,
    150613943, 241236829, 185515160,        12
  ],
  t: 74,
  s: 0
}
q:  BigInteger {
  data: [
     98203301, 223733815, 203915137,  61827841, 176325158,
     28126898, 197236893, 233459691, 175166922, 156510475,
    140175118,  93607278, 234033971, 126698219, 157373278,
    129017026,  38115043, 178090938, 101375046, 212813183,
       369530, 183636960,  35126850, 142381720, 212960678,
     44356007, 158170724, 142351731, 260278308, 142470691,
     11810266, 242194962, 220367199, 168665702,  35142346,
     54064991, 117567358,  85865792, 157955173, 256993948,
     36815051,  73689655, 210038972, 170809576,  63705308,
    118221656, 226960009, 179562201, 147022284,  58766204,
     81157877, 242987159,  10712508, 103036748, 131179580,
     50294077, 260192241, 210989067, 236361951, 179717270,
     53010107,  63385755, 251585604, 146299078, 260665602,
    180459045, 105975825,  67422926, 203219157, 108850612,
    124485495, 158915311, 170068408,        10
  ],
  t: 74,
  s: 0
}
-----
seed:  a9a6b63507dc2dedfac4afa8a2074c1d58fa97cc04901e9844ab937212567fa5
p:  BigInteger {
  data: [
    204819291, 125184622,  55213757,  41384530,  56329195,
    161802729, 237398828, 171976160, 242659852,  54680845,
      6379184, 128013249, 244497257,  18176204, 189753025,
     39047408, 239706085,  26783302,   7346839, 119806554,
    118802474,   3786056,  13456447, 173445427, 256995741,
    189070187,  63112685, 260143701, 191598716, 109140013,
     68189659,  30773098,  63978869,  89149752,   4307920,
    215590892,   3869222, 139890016,  64084517, 229392706,
    202435813, 129101180, 179767410, 244014137, 198460685,
    105485896,  72299551, 120998475,  78936425, 266471636,
    185225152, 189097146,   7723396,  34539926, 251950413,
     30479482,  34301206, 265663729, 118857769,  12785570,
     74972162, 160664107, 155496914, 179985101, 156964582,
     46179109, 122606868,  88861884, 244933372,  60989407,
    150613943, 241236829, 185515160,        12
  ],
  t: 74,
  s: 0
}
q:  BigInteger {
  data: [
     98203301, 223733815, 203915137,  61827841, 176325158,
     28126898, 197236893, 233459691, 175166922, 156510475,
    140175118,  93607278, 234033971, 126698219, 157373278,
    129017026,  38115043, 178090938, 101375046, 212813183,
       369530, 183636960,  35126850, 142381720, 212960678,
     44356007, 158170724, 142351731, 260278308, 142470691,
     11810266, 242194962, 220367199, 168665702,  35142346,
     54064991, 117567358,  85865792, 157955173, 256993948,
     36815051,  73689655, 210038972, 170809576,  63705308,
    118221656, 226960009, 179562201, 147022284,  58766204,
     81157877, 242987159,  10712508, 103036748, 131179580,
     50294077, 260192241, 210989067, 236361951, 179717270,
     53010107,  63385755, 251585604, 146299078, 260665602,
    180459045, 105975825,  67422926, 203219157, 108850612,
    124485495, 158915311, 170068408,        10
  ],
  t: 74,
  s: 0
}

Whether the Forge implemented PRNG with user provided seed can be used for generating deterministic but unique RSA keys? It seems the default prng is not uniform enough.

fai516 avatar Apr 07 '22 10:04 fai516