Project

General

Profile

Actions

Bug #7242

closed

Bignum mathematical accuracy regression in r31695

Added by mhall (Matthew Hall) over 9 years ago. Updated over 9 years ago.

Status:
Closed
Priority:
Normal
Target version:
ruby -v:
ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]
Backport:
[ruby-core:48552]

Description

We have some pure Ruby code which performs a DH (Diffie Hellman) cryptographic
handshake.

If I upgrade to using the Ruby 1.9.3 interpreter instead of 1.9.2, the unit
tests around the code fail, because the client and server can no longer
compute matching secret keys. I would expect they could agree on matching keys
as the DH algorithm expects. The code worked fine since May 2007 on Ruby 1.8
and 1.9 until the commit below was introduced.

Using svn-bisect, I was able to find that this commit from ruby-trunk in
between Ruby 1.9.2 (27656) and Ruby 1.9.3 (32500) causes the problem:

r31695 | mrkn | 2011-05-22 08:37:00 -0700 (Sun, 22 May 2011) | 4 lines

  • bignum.c (dump_bignum, bigmul1_balance, big_split, biglsh_bang,
    bigrsh_bang, big_split3, bigmul1_toom3, bigmul0): implement Toom3 (Toom-Cook)
    multiplication.
  • include/ruby/defines.h: add format prefixes for BDIGIT and BDIGIT_DBL.

Attached to this bug I have a simplified example test case which will pass
without this commit, and fail with this commit present.

Since this commit covers some relatively complex mathematical algorithms I'd
appreciate some assistance in finding the root cause from the experts on how
bignum.c works. I think the bug is relatively serious because it could cause
inaccurate output for other mathematical code using Bignums since it was
introduced in mid-2011.

This ruby -v comes from ruby trunk SVN at revision 31695, where the failure
begins to happen. I hand-re-compiled at the bisection points on trunk from
27655 through 32501 to identify the one which caused the problem.

$ ruby -v
ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]

C Compiler: gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

configure params:

./configure
--with-static-linked-ext
--prefix=/usr/local/ruby192
--enable-shared
--with-ruby-version=full


Files

dhtest.rb (1.2 KB) dhtest.rb test case code mhall (Matthew Hall), 10/30/2012 07:34 AM
dhtest.yaml (9.36 KB) dhtest.yaml test case data mhall (Matthew Hall), 10/30/2012 07:34 AM
toom3-bug.py.rb (3.64 KB) toom3-bug.py.rb mame (Yusuke Endoh), 10/30/2012 08:36 PM

Related issues 2 (0 open2 closed)

Related to Ruby master - Bug #6974: Functionality Loss in Bignum for Very Large Numbers (5.9 million digits)Closedmrkn (Kenta Murata)Actions
Related to Backport193 - Backport #7315: r37565 (bigmul1_toom3 のバグ回避) をバックポートしてくださいClosedusa (Usaku NAKAMURA)11/09/2012Actions
Actions

Also available in: Atom PDF