Prev: What do I need to know to design a cryptosystem?
Next: Is this construct a MAC ?
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 ?