Opened 13 years ago
Closed 12 years ago
#7746 closed enhancement (fixed)
Blum-Goldwasser probabilistic encryption
Reported by: | mvngu | Owned by: | mvngu |
---|---|---|---|
Priority: | major | Milestone: | sage-4.3.3 |
Component: | cryptography | Keywords: | Blum-Goldwasser, probabilistic encryption |
Cc: | wdj | Merged in: | sage-4.3.3.alpha1 |
Authors: | Minh Van Nguyen | Reviewers: | David Joyner |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
The Blum-Goldwasser probabilistic public-key encryption scheme. This scheme was originally described by (Blum and Goldwasser 1985). See also section 8.7.2 of (Menezes et al. 1996) and the Wikipedia article on this scheme.
- (Blum and Goldwasser 1985) M. Blum and S. Goldwasser. An Efficient Probabilistic Public-Key Encryption Scheme Which Hides All Partial Information. In Proceedings of CRYPTO 84 on Advances in Cryptology, pp. 289–299, Springer, 1985.
- (Menezes et al. 1996) A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996.
See #8246 for a follow-up ticket that implements the Carmichael lambda function.
Attachments (2)
Change History (9)
Changed 13 years ago by
comment:1 Changed 13 years ago by
- Cc wdj added
- Status changed from new to needs_review
The patch trac_7746-blum-goldwasser.patch
introduces two new files:
sage/crypto/public_key/blum_goldwasser.py
--- A class implementing the Blum-Goldwasser probabilistic public-key encryption scheme. This is a complete rewrite of the version by Mike Hogan and David Joyner, which was originally released as public domain software. The rewrite is licensed under GPLv2+. For reference, I have also attached the original public domain version.
sage/crypto/util.py
--- A module containing miscellaneous functions for cryptographic purposes. The Blum-Goldwasser implementation makes use of various functions in this module.
comment:2 follow-up: ↓ 3 Changed 13 years ago by
This applies and tests fine (modulo the usual failures) on sage-4.3.rc0 on a mac running 10.6.2.
This is definitely a complete reimplementation (as stated in the docstring) of Hogan's module, since we actually did a hybrid of the HAC version and the Wikipedia version of the algorithm.
I am not crazy about this:
289 However, if there are no primes between the lower and upper bounds, 290 this function could hang forever. For instance, a lower bound of 24 and 291 an upper bound of 28 would trigger an infinite loop.
It seems to violate the "defensive programming" (or "assume all people are stupid") principle that if the is some very bad input which can be entered, then you should assume that it *will* be entered at some point.
Other than this, the patch looks very well documented, gives good references and examples. I've forgotten how to compile the docs to see if the html comes out okay. Can someone point to a page in the Developers' manual of something where html generation is explained? I don't see the changes in
sage-4.3.rc0/devel/sage-BG-7746/doc/output/html/en/reference/sage/crypto/cryptosystem.html
Finally, some general more-or-less stylistic questions.
Is SageObject? the best superclass for this?
Is the best place for blum_blum_shub in util or in a stream cipher module?
comment:3 in reply to: ↑ 2 ; follow-up: ↓ 4 Changed 13 years ago by
- Status changed from needs_review to needs_work
Replying to wdj:
It seems to violate the "defensive programming" (or "assume all people are stupid") principle that if the is some very bad input which can be entered, then you should assume that it *will* be entered at some point.
It looks to me that there needs to be a function called, say, "has_blum_prime(lbound, ubound)" in the module sage/crypto/util.py
. This function checks to see if there is a Blum prime within the specified lower and upper bounds. One could then use has_blum_prime()
to first check for the presence of a Blum prime within a specified interval, prior to actually computing a random Blum prime.
Can someone point to a page in the Developers' manual of something where html generation is explained? I don't see the changes in
After you have applied the patch and rebuilt your branch, you could use the following command to rebuild the HTML version of the reference manual:
./sage -docbuild reference html
Is SageObject? the best superclass for this?
No, not really. Ideally, the best parent class for the class BlumGoldwasser
is sage.crypto.cryptosystem.PublicKeyCryptosystem
. I'll see what I can do to make sage.crypto.cryptosystem.PublicKeyCryptosystem
the parent class of BlumGoldwasser
.
Is the best place for blum_blum_shub in util or in a stream cipher module?
I think the best place for the function blum_blum_shub()
is in a module for pseudorandom number generators. The module that comes to mind is sage/misc/prandom.py
. But all functions in that module are exported to the global name space, so those functions are available upon starting Sage, without having to explicitly import them. Adding more functions to the global name space is not a good idea. One wants to minimize Sage's loading time, but also to have a default set of common useful functions. Adding blum_blum_shub()
to sage/misc/prandom.py
and polluting the global name space is not my intention. The Blum-Blum-Shub pseudorandom bit generator is not as commonly used as, say, random()
and randint()
. For now, blum_blum_shub()
fits OK in sage/crypto/util.py
. Functions in that module are not exported by default, which is why you see lots of import statements throughout examples in that module.
comment:4 in reply to: ↑ 3 ; follow-up: ↓ 5 Changed 13 years ago by
Replying to mvngu:
Replying to wdj:
It looks to me that there needs to be a function called, say, "has_blum_prime(lbound, ubound)" in the module
sage/crypto/util.py
. This function checks to see if there is a Blum prime within the specified lower and upper bounds.
Sounds good.
use the following command to rebuild the HTML version of the reference manual:
./sage -docbuild reference html
Thanks. Docs compile fine and look great.
Is the best place for blum_blum_shub in util or in a stream cipher module?
I think the best place for the function
blum_blum_shub()
is in a module for pseudorandom number generators. The module that comes to mind issage/misc/prandom.py
. But all functions in that module are exported to the
Why not
sage/crypto/stream_cipher.py
instead?
comment:5 in reply to: ↑ 4 Changed 12 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
Replying to wdj:
Sounds good.
I have attached an updated patch which also implements the function has_blum_prime()
.
Why not
sage/crypto/stream_cipher.py
instead?
The module sage/crypto/stream_cipher.py
acts as a back-end for sage/crypto/stream.py
. I believe a more appropriate place is to put blum_blum_shub()
in sage/crypto/stream.py
. The latest version of the patch does this.
comment:6 Changed 12 years ago by
- Status changed from needs_review to positive_review
Applied fine to 4.3.3.a0 and passes sage -testall. Reference manual looks good too.
Positive review.
Thank you very much Minh!
comment:7 Changed 12 years ago by
- Merged in set to sage-4.3.3.alpha1
- Resolution set to fixed
- Reviewers set to David Joyner
- Status changed from positive_review to closed
public domain version by Mike Hogan and David Joyner