lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
Open Source and information security mailing list archives
| ||
|
Message-ID: <540A0506.8070204@ciphershed.org> Date: Fri, 05 Sep 2014 14:46:30 -0400 From: Bill Cox <waywardgeek@...hershed.org> To: discussions@...sword-hashing.net Subject: Re: [PHC] A review per day - Makwa -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 09/05/2014 01:40 PM, Bill Cox wrote: > A property that these groups share is that the order of any > particular sub-group starting with any residue of n minus 1 divides > numMaxOrder. NumMaxOrder is always (p-3)/2, which is even because p > is = 3 mod 4. If we just want to avoid the worst bad primes, we > could require that (p-3)/4 be equal to twice a prime. This works really well! I'm calling Makwa primes (safe primes == 3 mod 4) "solid" Makwa primes if (p-3)/4 is also prime. Here's the list of solid Makwa primes below 10,000: Solid primes: 11, 23, 47, 167, 359, 719, 1439, 2039, 2879, 4079, 4127, 4919, 5639, 5807, 5927, 6047, 7247, 7559, 7607, 7727, 9839 - From the previous runs, I see that squaring groups modulo a Blum integer n = p*q, where p and q are Makwa primes, that there will always be exactly 4 sizes of groups: 1-long: 3 residues total (including 1) factor of (p-3)/2 long: p-3 residues factor of (q-3)/2 long: q-3 residues factor of (p-3)*(q-3)/2: (p-3)*(q-3)/4 residues This is simply an observation, not a proof. Some work would have to be done by some more number theory inclined person than me to show this formally. When (p-3)/4 is prime, and (q-3)/4 is prime, then (p-3)*(q-3)/4 is a multiple of 4 times two large primes. The only way this splits is either into 2 or 4 sets of quadratic residues, meaning that the cycle length when using "solid" Makwa primes is: cycle length >= (p-3)*(q-3)/16 For large p and q, this is aproximately 1/16th of n, or only a loss of at 2 bits. It looks like we could guarantee this strength. The code is very simple to write. The main downside is that "solid" primes are a small subset of Makwa primes. They are quite a bit harder to find than safe primes. Here's 10 random results with solid Makwa primes, demonstrating the strength of this concept: Finding totals for 6047 4127 Average = 1 , distribution = {1557841: 6231364, 1031: 4124, 1511: 6044, 1: 3} , chance of sub-optimal = 0.162956708566 % Finding totals for 7247 5639 Average = 1 , distribution = {1: 3, 2818: 5636, 1811: 7244, 5103398: 10206796} , chance of sub-optimal = 0.126060710909 % Finding totals for 6047 7559 Average = 1 , distribution = {1: 3, 3778: 7556, 5708558: 11417116, 1511: 6044} , chance of sub-optimal = 0.119003887682 % Finding totals for 7727 5807 Average = 1 , distribution = {2801881: 11207524, 1451: 5804, 1931: 7724, 1: 3} , chance of sub-optimal = 0.120585809445 % Finding totals for 6047 9839 Average = 1 , distribution = {1: 3, 2459: 9836, 3715549: 14862196, 1511: 6044} , chance of sub-optimal = 0.10675437333 % Finding totals for 9839 5927 Average = 1 , distribution = {1: 3, 2962: 5924, 2459: 9836, 7283558: 14567116} , chance of sub-optimal = 0.108092510402 % Finding totals for 7247 7559 Average = 1 , distribution = {1: 3, 3778: 7556, 1811: 7244, 6841958: 13683916} , chance of sub-optimal = 0.108061199007 % Finding totals for 5639 7607 Average = 1 , distribution = {1: 3, 5357018: 10714036, 2818: 5636, 3802: 7604} , chance of sub-optimal = 0.123451622727 % Finding totals for 9839 5639 Average = 1 , distribution = {1: 3, 2818: 5636, 2459: 9836, 6929462: 13858924} , chance of sub-optimal = 0.111536362764 % Maybe I should read the rest of the Makwa paper... but I finished the security section, and there was no mention of picking safe primes, but that goes without saying, and no mention of other requirements other than p == 3 mod 4. Is this test already taken into account when picking Makwa primes? Bill -----BEGIN PGP SIGNATURE----- Version: GnuPG v1 iQIcBAEBAgAGBQJUCgUDAAoJEAcQZQdOpZUZD68P/1zW0dUluGS15hEVgveIQsdT q+4FHUTCvxmQZABgTvwg6C8VcUybgG+kGqfSwD4x4M0GYg3yKDk9XR4IeYrAbwUT Z6tl9esgUAP8HXCsXh8Ox7uF/XONaelxxN1ZuAaMxhCU27LRn61BTy0a9v3dLd7Q OHQjzMRxOwMzGbNZYSKtLXB4Zmhv6gMIoNr1mfhkXjKXvb3YQu6Orz875uxuxZVQ /TU9nvHaSsB6zBiF8GTlbBOwEytL41Ib+FZ+7sYZv/JgSuPdUWFk5HgPTPHiZJRA bovjmWMGzSKnf533zb27CMdWdnhOge9Q4NAV+T6cjkBlZxSs2OyU0A2em4IW+HBS ZCrUpwK1eI9MgFuwZBdrAP6Ekgra6cEkVrZgDaI5gYanCj6VCvy0BI2ZrRolz61c JGtziOJe8OU+1wMLTR/z/EPC1rWs+QgQGFEYJxDYC7v4gjFYqLwIPXeYLFnx5F65 s2iVQlYpwFWIR0LWSlm0LogzpZNkgBP/wSxjiGYcPjbusXAKbLPhOP5qT/L1pCbf dslP8fhEGq3rW+M20mN0C2EfyPRzzdQRt/JsVxOUwrUyYJ9Ph60NolMLxzpBmbpJ CxLAQ5Snd8QTOkVN31ixr1C0Vw/99PBiSSo1k/sI+yPIjznpVBPElnAaIB6eVlyd rqnfTvVhcRx5YkMQc4M5 =EItL -----END PGP SIGNATURE-----
Powered by blists - more mailing lists