Opened 3 years ago

Closed 3 years ago

#24282 closed defect (fixed)

BooleanFunction.truth_table(format="hex") returns wrong values

Reported by: pleopardi Owned by:
Priority: major Milestone: sage-8.2
Component: cryptography Keywords:
Cc: Merged in:
Authors: Paul Leopardi Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: eeaebe3 (Commits) Commit: eeaebe309317a0df13b561db53384d5b758a61af
Dependencies: Stopgaps:

Description (last modified by dimpase)

Sometimes, especially with functions of 8 variables, the method BooleanFunction.truth_table(format='hex") returns incorrect values that are also too long.

Example:

sage: from sage.rings.integer_ring import ZZ
sage: from sage.crypto.boolean_function import BooleanFunction
sage: hex_str = "0123456789112345678921234567893123456789412345678951234567896123"
sage: len(hex_str)
64
sage: bf = BooleanFunction(hex_str)
sage: bf.nvariables()
8
sage: bf_tt_hex = bf.truth_table(format="hex")
sage: bf_tt_hex
'123456789112345678921234567893123456789412345670123456789112345678921234567893123456789412345678951234567896123'
sage: len(bf_tt_hex)
111
sage: S = ZZ(bf.truth_table(), 2).str(16)
sage: padding = "0" * ((1 << (bf.nvariables() - 2)) - len(S))
sage: tt_hex = padding + S
sage: tt_hex
'0123456789112345678921234567893123456789412345678951234567896123'
sage: len(tt_hex)
64

The example also shows how the code in https://github.com/sagemath/sage/blob/develop/src/sage/crypto/boolean_function.pyx lines 566 to 576 should be fixed. A suggested patch is attached.

The example can also be used as the basis for a test case once the patch has been applied.

Attachments (1)

boolean_function-correct_truth_table_hex.patch (844 bytes) - added by pleopardi 3 years ago.
Patch to boolean_function.pyx to retrun correct value for truth_table(format='hex')

Download all attachments as: .zip

Change History (11)

Changed 3 years ago by pleopardi

Patch to boolean_function.pyx to retrun correct value for truth_table(format='hex')

comment:1 Changed 3 years ago by dimpase

  • Description modified (diff)
  • Milestone changed from sage-8.1 to sage-8.2

Thanks. Could you provide a test example and a git branch for the fix, too?

comment:2 Changed 3 years ago by pleopardi

A working test example may take me a little time as I have not yet built Sage from Git. I could mock up a test example for someone else to test, if that is acceptable.

comment:3 Changed 3 years ago by pleopardi

Also, I am new at providing Git branches for Sage. I will carefully read the instructions at http://doc.sagemath.org/html/en/developer/manual_git.html and use them to provide a Git branch. This may have to wait until the weekend.

comment:4 Changed 3 years ago by pleopardi

  • Branch set to u/pleopardi/fix_boolean_function_truth_table_hex
  • Commit set to d22ccd3ccd1e79d5f6153e54c0dbefa89bf93139
  • Status changed from new to needs_review

As far as I can tell, I have pushed my recommended changes to the branch u/pleopardi/fix_boolean_function_truth_table_hex

This is the first time I have created a branch in trac, so I may have made a mistake that I'm not aware of.

comment:5 Changed 3 years ago by dimpase

I would have cut most of these

sage: len(T)
...

from the example in your branch. Have you tried building the documentation with this branch applied?

comment:6 Changed 3 years ago by git

  • Commit changed from d22ccd3ccd1e79d5f6153e54c0dbefa89bf93139 to eeaebe309317a0df13b561db53384d5b758a61af

Branch pushed to git repo; I updated commit sha1. New commits:

eeaebe3Remove some len expressions from doctest for BooleanFunction.truth_table

comment:7 Changed 3 years ago by pleopardi

I have now cut some of the len expressions from the doctest, have retested sage/crypto, and have tried rebuilding the documentation. All seems fine to me.

comment:8 Changed 3 years ago by dimpase

  • Reviewers set to Dima Pasechnik
  • Status changed from needs_review to positive_review

Looks good to me; however, it probably needs testing on a 32-bit machine. Hopefully a patchbot will do.

PS. Please enter the author's name in Authors.

comment:9 Changed 3 years ago by pleopardi

  • Authors set to Paul Leopardi

I have added my name to Authors.

comment:10 Changed 3 years ago by vbraun

  • Branch changed from u/pleopardi/fix_boolean_function_truth_table_hex to eeaebe309317a0df13b561db53384d5b758a61af
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.