Opened 6 years ago

Closed 6 years ago

#20336 closed enhancement (fixed)

Add more features to mq.SBox

Reported by: ruhm Owned by:
Priority: major Milestone: sage-7.2
Component: cryptography Keywords: SBox, cryptography
Cc: malb Merged in:
Authors: Rusydi H. Makarim Reviewers: Travis Scrimshaw, Martin Albrecht
Report Upstream: N/A Work issues:
Branch: 05bc98b (Commits, GitHub, GitLab) Commit: 05bc98b0e59ecf4a124881fc60a8b27179295bb0
Dependencies: Stopgaps:

Status badges

Description (last modified by ruhm)

Current implementation of mq.SBox is still lack of basic functionality to determine various cryptographic properties of an S-Box such as nonlinearity, differential uniformity, etc. This commit implements some of them such as :

  1. Computation of nonlinearity and differential uniformity.
  2. Determine if the S-Box is an almost bent (AB) / almost perfect nonlinear function (APN).
  3. Determine the balancedness of the S-Box.
  4. Compute the maximum and minimum algebraic degree of its component function.
  5. Obtain the component function.
  6. Compute its the differential and linear branch number.
  7. Compute its autocorrelation matrix.
  8. Obtain linear structures in its component functions.
  9. Obtain all fixed points in the S-Box.
  10. For an invertible S-Box, obtain its inverse.
  11. Determine if the S-Box is a monomial function.

Change History (14)

comment:1 Changed 6 years ago by ruhm

  • Branch set to u/ruhm/improved_sbox

comment:2 Changed 6 years ago by ruhm

  • Authors set to Rusydi H. Makarim
  • Commit set to 1b081175e82e322d598e02448414654f2245ef14
  • Component changed from PLEASE CHANGE to cryptography
  • Keywords SBox cryptography added
  • Status changed from new to needs_review
  • Type changed from PLEASE CHANGE to enhancement

New commits:

1b08117Enhancement: Provide functionality to determine various cryptographic properties of S-Box

comment:3 Changed 6 years ago by ruhm

  • Description modified (diff)

comment:4 follow-up: Changed 6 years ago by tscrim

I can't comment to much on the code itself since it is outside of my expertise. However, I can make some comments on formatting:

  • Instead of $ for latex, you should use `. (We do support the former, but it is not as well-supported as the latter.)
  • Instead of \mathbb{F}_2, you should use the macro \GF{2} for consistency with the rest of Sage.
  • Error statements are not sentences, and as such, should not start with a uppercase letter nor have a period. This is also to be consistent with Python.
  • The input block should be formatted like this:
          - ``b`` -- either an integer or a tuple of `\GF{2}` elements of
            length ``self.n``
    
  • Remove the unnecessary parentheses here: return (self.differential_uniformity() == 2).
  • It is better to use \mathrm{wt} or \operatorname{wt} instead of \text{wt} (this is a latex thing having to do with spacing rules).
  • You should use .. MATH:: and have the equation indented on a separate line (with a blank line inbetween).
  • Try to keep lines less than 80 characters long
  • autocorrelation_matrix should be a @cached_method. Also make sure it returns an immutable matrix.
  • All parentheses are extraneous here: if ((m & 1) == 0):. At least the outer ones are.
  • I prefer EXAMPLES:: even when there is only one example; more maybe added later and this is for consistency.
  • In the doc, do ``TypeError``.

Otherwise the doc and coding style looks good. I could try to review the code if no one else steps forward.

Also is this your first contribution to Sage?

comment:5 Changed 6 years ago by malb

  • Cc malb added

comment:6 Changed 6 years ago by git

  • Commit changed from 1b081175e82e322d598e02448414654f2245ef14 to 38b627e25ee6525ec6ffd83d55ecbeea574ea155

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

38b627evarious fixes based on the initial comment.

comment:7 in reply to: ↑ 4 Changed 6 years ago by ruhm

Hi,

Thanks, I have updated it according to the initial comment. And yes, this is my first contribution to SAGE.

-- Rusydi

Replying to tscrim:

I can't comment to much on the code itself since it is outside of my expertise. However, I can make some comments on formatting:

  • Instead of $ for latex, you should use `. (We do support the former, but it is not as well-supported as the latter.)
  • Instead of \mathbb{F}_2, you should use the macro \GF{2} for consistency with the rest of Sage.
  • Error statements are not sentences, and as such, should not start with a uppercase letter nor have a period. This is also to be consistent with Python.
  • The input block should be formatted like this:
          - ``b`` -- either an integer or a tuple of `\GF{2}` elements of
            length ``self.n``
    
  • Remove the unnecessary parentheses here: return (self.differential_uniformity() == 2).
  • It is better to use \mathrm{wt} or \operatorname{wt} instead of \text{wt} (this is a latex thing having to do with spacing rules).
  • You should use .. MATH:: and have the equation indented on a separate line (with a blank line inbetween).
  • Try to keep lines less than 80 characters long
  • autocorrelation_matrix should be a @cached_method. Also make sure it returns an immutable matrix.
  • All parentheses are extraneous here: if ((m & 1) == 0):. At least the outer ones are.
  • I prefer EXAMPLES:: even when there is only one example; more maybe added later and this is for consistency.
  • In the doc, do ``TypeError``.

Otherwise the doc and coding style looks good. I could try to review the code if no one else steps forward.

Also is this your first contribution to Sage?

comment:8 Changed 6 years ago by tscrim

  • Reviewers set to Travis Scrimshaw

Welcome to Sage! This is a very well-done submission.

Now that you are using @cached_method, you don't need the _autocorrelation_matrix attribute and can remove this code:

        try:
            return self._autocorrelation_matrix
        except AttributeError:
            pass

(similarly for the linearly_approximation_matrix).

Martin, will/can you be doing a review of the math parts?

comment:9 Changed 6 years ago by malb

Hi all, I took a look at the ticket. It's very nice! The only thing I noticed is that you're adding new functions for differential_uniformity. Wouldn't an alias be sufficient, e.g. differential_uniformity = maximal_difference_probability_absolute?

comment:10 Changed 6 years ago by malb

PS: We should move mq.SBox to some other place. It has almost nothing to do with MQ any more, it's much more general now. But that's another ticket.

comment:11 Changed 6 years ago by git

  • Commit changed from 38b627e25ee6525ec6ffd83d55ecbeea574ea155 to 05bc98b0e59ecf4a124881fc60a8b27179295bb0

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

05bc98bcleanup linear approx matrix and autocorrelation matrix, aliasing differential_uniformity

comment:12 Changed 6 years ago by tscrim

This is good from my viewpoint.

comment:13 Changed 6 years ago by malb

  • Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Martin Albrecht
  • Status changed from needs_review to positive_review

Same here.

comment:14 Changed 6 years ago by vbraun

  • Branch changed from u/ruhm/improved_sbox to 05bc98b0e59ecf4a124881fc60a8b27179295bb0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.