From: stevenvh on 10 May 2010 10:43 Hi, let the one-way function be (a ^ b) mod m. What are typical ranges for a, b and m? I guess a can be small ( 10^1 ?) since (a ^ b) becomes rather large very quickly. TIA Steven
From: Tom St Denis on 10 May 2010 12:15 On May 10, 10:43 am, stevenvh <steven.ne...(a)gmail.com> wrote: > Hi, > let the one-way function be (a ^ b) mod m. What are typical ranges for > a, b and m? I guess a can be small ( 10^1 ?) since (a ^ b) becomes > rather large very quickly. > TIA > Steven What do you mean small? like they're all on the order of at most 2 digits? No. DH is normally computed over 300+ digit [decimal] numbers. tom
From: Bryan on 10 May 2010 14:35 stevenvh asked: > let the one-way function be (a ^ b) mod m. What are typical ranges for > a, b and m? I guess a can be small ( 10^1 ?) since (a ^ b) becomes > rather large very quickly. Yes, the base can be small, as long as it generates a large subgroup of the multiplicative group mod m. RFC 3526 specifies some groups for Diffie-Hellman key exchange that use 2 as the base. You can find more guidance on sizes in: http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf -- --Bryan
From: bert on 11 May 2010 04:32 On 10 May, 15:43, stevenvh <steven.ne...(a)gmail.com> wrote: > Hi, > let the one-way function be (a ^ b) mod m. What are typical ranges for > a, b and m? I guess a can be small ( 10^1 ?) since (a ^ b) becomes > rather large very quickly. You're new to this, aren't you? (a^b) mod m is computed by a binary power ladder in approximately 1.5 * log2(b) steps. As the answer can be reduced modulo m at each stage, intermediate results never exceed m, however large a and b are. For a trivial example, to compute a^77, one computes in turn a^(2, 4, 8, 9, 18, 19, 38, 76, 77), where at each stage one either squares, or multiplies by a. --
From: Maaartin on 11 May 2010 05:28 On May 11, 4:32 am, bert <bert.hutchi...(a)btinternet.com> wrote: > On 10 May, 15:43, stevenvh <steven.ne...(a)gmail.com> wrote: > > > Hi, > > let the one-way function be (a ^ b) mod m. What are typical ranges for > > a, b and m? I guess a can be small ( 10^1 ?) since (a ^ b) becomes > > rather large very quickly. > > You're new to this, aren't you? > > (a^b) mod m is computed by a binary power ladder in > approximately 1.5 * log2(b) steps. As the answer > can be reduced modulo m at each stage, intermediate > results never exceed m, however large a and b are. > > For a trivial example, to compute a^77, one computes > in turn a^(2, 4, 8, 9, 18, 19, 38, 76, 77), where at > each stage one either squares, or multiplies by a. I think, you don't answer what he asked. His concern seems to be the fact, that with small a and b, it could happen that a**b < m, which would mean that no modular reduction happens and a could be recovered simply by taking the b-th root in real numbers.
|
Next
|
Last
Pages: 1 2 3 Prev: What do I need to know to design a cryptosystem? Next: Is this construct a MAC ? |