Opened 10 years ago

Closed 10 years ago

#6454 closed enhancement (fixed)

[with patch, positive review] improve sbox linear and differences matrices computation

Reported by: ylchapuy Owned by: somebody
Priority: minor Milestone: sage-4.1.1
Component: cryptography Keywords:
Cc: malb Merged in: sage-4.1.1.alpha0
Authors: Yann Laigle-Chapuy Reviewers: Martin Albrecht
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

In particular, use walsh transform for linear_approximation_matrix.

Attachments (2)

trac_6454_sbox.patch (2.8 KB) - added by ylchapuy 10 years ago.
trac_6454_review.patch (1.0 KB) - added by ylchapuy 10 years ago.

Download all attachments as: .zip

Change History (9)

Changed 10 years ago by ylchapuy

comment:1 Changed 10 years ago by ylchapuy

  • Cc malb added
  • Summary changed from improve sbox linear and differences matrices computation to [with patch, needs review] improve sbox linear and differences matrices computation

comment:2 Changed 10 years ago by malb

  • Summary changed from [with patch, needs review] improve sbox linear and differences matrices computation to [with patch, needs work] improve sbox linear and differences matrices computation

Hi there, it is embarrassing how bad my naive original code was. Here's a comparison (for the release tour)

Old*

sage: S = mq.SR(1,4,4,8).sbox()
sage: %time _ = S.difference_distribution_matrix()
CPU times: user 82.14 s, sys: 0.01 s, total: 82.15 s
Wall time: 82.15 s

sage: %time _ = S.linear_approximation_matrix()
CPU times: user 145.10 s, sys: 0.02 s, total: 145.12 s
Wall time: 145.12 s

*New*

sage: S = mq.SR(1,4,4,8).sbox()
sage: %time _ = S.difference_distribution_matrix()
CPU times: user 0.32 s, sys: 0.00 s, total: 0.32 s
Wall time: 0.32 s
sage: %time _ = S.linear_approximation_matrix()
CPU times: user 1.10 s, sys: 0.00 s, total: 1.10 s
Wall time: 1.10 s

The code looks good, doctests pass.

The only issue: the sage -coverage script will pick up _walsh_transform and complain that it isn't documented and doctested.

Of course it is impossible to doctest this inner function directly, but the keyword # indirect doctest will do the trick.

This is a positive review except for the missing documentation.

Changed 10 years ago by ylchapuy

comment:3 Changed 10 years ago by ylchapuy

  • Reviewers set to Martin Albrecht

Both patches should be applied.

I added an indirect doctest. I give myself a positive review, feel free to correct me if you disagree.

comment:4 Changed 10 years ago by ylchapuy

  • Summary changed from [with patch, needs work] improve sbox linear and differences matrices computation to [with patch, positive review] improve sbox linear and differences matrices computation

comment:5 Changed 10 years ago by malb

All good, definitively a positive review.

comment:6 Changed 10 years ago by mvngu

Just to let people know, this has been merged in sage-4.1.1-alpha0. I can't close this ticket because I don't have the privilege to do so. Sorry, folks :-(

comment:7 Changed 10 years ago by mvngu

  • Merged in set to sage-4.1.1.alpha0
  • Resolution set to fixed
  • Status changed from new to closed
Note: See TracTickets for help on using tickets.