[Repo] Num-Primes | @AtropineTearz

Num-Primes is a memory-safe CSPRNG for generating large composite, prime, and safe prime numbers. It also allows for verification of primality (although there is still one issue being fixed that prevents verification from working properly for some numbers).

This can be compared to OpenSSL's random number generator except that it is memory safe and supports no_std for embedded systems.

It also supports verification of very smooth numbers and factorization.

I did post this awhile back but I have posted it here so others can see. If you are new to /r/PrimitivePlayground, stay awhile :)

I came up with an interesting concept while attempting to formulate an objective mechanism for concealing cipher state under known plaintext attacks: I decided to call it "Cryptographic Convolution"

A cryptographic convolution is here defined as a convolution of a circular array of symbols, wherein the convolution kernel at each point is varied based on the value of the symbol in the source array at the sampling point (or in a more complex usage, determined by the value sample taken from another convolution operation on the source array at that point). This variable kernel may be either an entry from a table of kernels (static), or it may be derived from the values taken from the source array (dynamic). In this context, "Convolution" also does not need to require or imply a weighted summation of inputs - any function which accepts any number of symbols and outputs a single symbol can also fit into the concept.

The intent of this operation is to provide a transform which strongly entangles any dependent products with its source data without leaking any *useable information about its source data, but which is also very computationally cheap.

(*) Could also be thought of as ensuring that the information that leaks is objectively ambiguous.

Below are some worked examples for the dynamic kernels (treating symbols at positions +0 and +1 relative to the symbol referenced by the sample point)

The first example (and the only one that uses random data) is spelled out with the following notation -- :Sample [kernel] +addend ->result

5 8 1 9 6 0 2 3 4 7
6 4 4 9 5 4 3 1 0 0

+:5   8  +1   9   6  [0   2]  3   4   7   -> 6
  5  :8   1   9   6  +0   2   3 [+4   7]  -> 4
 +5  [8  :1] +9   6   0   2   3   4   7   -> 4
 +5]  8   1  :9   6   0   2   3  +4  [7   -> 9
  5   8   1   9  :6   0 [+2  +3]  4   7   -> 5
[+5   8]  1  +9   6  :0   2   3   4   7   -> 4
  5   8  [1   9]  6  +0  :2  +3   4   7   -> 3
  5   8   1 [+9   6]  0  +2  :3   4   7   -> 1
  5   8   1   9 [+6   0]  2   3 +:4   7   -> 0
  5   8  +1  +9   6   0   2  [3   4] :7   -> 0

0 1 2 3 4 5 6 7 8 9
1 5 9 3 7 1 5 9 3 7

0 9 1 8 2 7 3 6 4 5
5 2 7 0 8 4 6 8 7 4

Might seem a bit scary on simple patterns... But it's the ambiguity that counts!

3 6 9 2 5 8 1 4 7 0
7 7 7 7 7 7 7 7 7 7

0 3 6 9 2 5 8 1 4 7
9 9 9 9 9 9 9 9 9 9

Static kernels are also ambiguous when attempting to invert (or so I claim, but don't particularly want to fill this post with numbers over), but they use less of the actual source data and the lookup into a static table is about as much work as the dynamic lookup, and presumably are somewhat more predictable.

Observations:
In general, a cipher should only compute a single sample from a cyptographic convolution, then alter the source data in some manner (preferably an alteration which prevents the same symbols from being referenced to produce the same output for the same reason [should suffice to move the symbol at the sample point or move both immediately adjacent symbols]). Care should also be taken in cipher design to prevent would-be attackers from obtaining a complete or useably ordered cryptographic convolution (for more ambiguity).

Conjectures: If used to turn random data into a keystream (each random symbol used once then discarded), I do not expect the random data stream to be recoverable from the resulting keystream by any means. If the underlying data is used to determine the amount of terms, weights of terms, and positions of generating symbols for dynamic convultion kernels, then inverting a complete convolution seems like it should be equivalent to brute-forcing the underlying data.

Motivation: I am [still] thinking about hand-operated ciphers, still like the idea of deriving an encryption operation from some permutation of a set of symbols, and still want to stick to very simple operations. But (due largely to various attacks on RC4 and its variants) I have also determined that directly outputting any symbol in the cipher state leaks too much information about the cipher state (even if state transitions are very complex).

This came out of another experiment where I applied a convolution with modular addition to a circular array of random values using modular addition as an operator (to get a better sense of what I was doing with cipher design), then observed that the de-convolutions were a set of predictable but ambiguous transformations of the original data. Varying the kernel based on the value at the sample point eliminated the predictability and greatly increased the ambiguity - more de-convolutions to match a given output, and I could even get branching matches (multiple unique de-convolutions could start with the same guessed sequence, then deviate).

About

All these crates are open source and reference implementations of the hash based cryptographic schemes Lamport Signatures and Winternitz One Time Signatures.

They are all coded in Rust and have simple API to use.

Lamport Signatures

Star it on Github

Use the Crate

This crate gets its randomness from the operating systems CSPRNG. It also can use three different hash functions (SHA256,SHA512,Blake2b), two of which are wrappers around the operating systems hash functions with one (Blake2b) being from a rust library.

It can sign up to 512 bits (64 bytes) with an input of a hexadecimal string. It implements serde.

Winternitz-OTS Library

Star it on Github

Use the Crate

By default, it uses a winternitz parameter (w) of 16 and can sign up to 256 bits (32 bytes) in hexadecimal.

Hey.

Lately I'm mostly interested in paper & mental cryptography, but I've been looking for some glitch sites and after 20 minutes of playing with this realized there could be something interesting with unicode to look at more closely.

So I've found this gltich text generator, and realized it's bijective if you use regular text, but if you use an emoji it's actually a surjection - I think that's the correct term for "I can turn some emoji into a glitch text and I can't turn that glitch text back to emoji", so if I'm using the term wrongly I hope you correct me :) https://lingojam.com/GlitchTextGenerator

I tried to look at the binary version of the output (I used some text to binary converter online) when using 1 emoji and then comparing that with the output when I just added 1 more emoji to the first one - the difference was like 97% (not around 50% that I expected).

Basically from all of that it looks to me as it satisfies some of the most important demands for a good hash function, but I'm sure some of you can deny or confirm that more quickly than me, so I decided to share it here, maybe someone will share the same curiosity, and at least have some fun with this. Because you gotta admit, even if the possibility of an emoji-filled glitch text generator being a hash function (which would be totally hillarious) is non-existant, this has got to be one of the funniest titles on a crypto-related reddit post you've seen in some time. :D

Btw I'm not trolling, just exploring the world of crypto through some really superficial and more artsy-like ways. I'm also reading and researching serious topics on the side, but I've realized this type of thing allows me to not only better understand some concepts myself, but also to better explain them to other people and help expand the awareness about the need of information security. I'm playing around with it basically, so I thought this to be a good place to share the play.

Hi everyone,

I've been kicking around an idea that I call a Moving Window Full Domain Hash. It's basically a way to efficiently transform a extendable hash function like SHA3 into a fix-width hash function of arbitrary length but within a specific domain.

It might be used for things like RSA blind-signature scheme where the digest needs to be less than modulus n.

Here's a link to the write-up of the idea: https://github.com/phayes/fdh-rs/tree/master/src/movingwindow

Feedback welcome!

I am trying to find a (new?) way to implement PFS in a message chain. The idea is as follows:

• a message chain has a state which is derived from pre-shared secret
• a new message changes the message chain state
• new message's confidentiality is derived from previous message chain state i.e. to send a new message, old message chain state must be known
• previous state can not be found out from current state (PFS part)
• previous state can be validated without full access to all previous messages (access to some recent messages is available)

Would this work? How would you do it?

The last point seems tricky, with zk-SNARKs or with something less complex?

Thanks!

If you prefer to skip my explanation as I know I can type a lot and just read the paper:

• [Paper] HALO Academic Paper

• [Implementation] HALO Rust Crate

• [Article] Halo: Recursive Proof Composition without a Trusted Setup

This comes from the team behind Zcash, who have done some really interesting work in the ZKP field, such as introducing the BLS12-381 Elliptic Curve, and also creating the zk-SNARKs rust crate, bellman.

Also, this is something I have been really, really interested in for quite some time now so sorry if I sound like a 5 year old in a candy store with over-explaining everything. I just think that ZKPs don't get nearly enough attention for what they can do. And with the information about this having just been released and the news that Recursive Composition can now be done without a trusted setup,

Explanation

You may all be interested in a paper that just came out. Recursive Composition of zk-SNARKs allows for you to continually create proofs and only keep the current state proof, and this proof remains constant in size, even over time. Even moreso, is that these proofs are stupidly fast to validate and like the proof size, remain constant in their validation speed.

This paper presents it without a need for a trusted setup for the zk-SNARKs, which is pretty big. I honestly think more people should look into this type of technology and seriously consider its use for lots of things, because ZKPs themselves are really powerful, and when done recursively, you can prove the validity of a change in state.

To add to this, it does not use pairing-friendly elliptic curves but only ordinary elliptic curves for its proof.

Why Should I Even Care About This Technology?

I think most people don't fully understand that Zero-Knowledge Proofs and things like zk-SNARKs are not just something like, RSA, for example. By that I mean that zk-SNARKs and ZKPs can be used in MANY different instances, as long as you can setup the circuit for it and the problem is NP-complete. For example, in Zero-Knowledge, I can prove that I know the preimage to a hash, such as in ZkBoo, without ever revealing anything besides the validity of the statement. And theres so many benefits to using NIZKPs, such as constant proof size, stupidly fast validation even with increased circuit complexity, and the ability to solely prove the validity of a statement and nothing else.

While ZKPs have been known since the 80s, it had not become practical up until about a few years ago, and increasingly, it is getting more and more attention, and for good reason. My hope is that others who have seen Zero-Knowledge Proofs mentioned but aren't really sure what they are look into them more, and this includes developers.

For a related subject, the CODA Protocol uses a form of Recursive Composition of zk-SNARKs to compress large blockchains to a constant size and allows anyone to be able to get the blockchain's current state by simply having the ~600byte zk-SNARK proof. The chain required a trusted setup.

CODA Protocol:

• Whitepaper

• Zk-SNARK [BG18]

• Podcast - Digging into recursive zkSNARKs with Coda

This concept came to me after a bit of a bender on IBM's MVS 3.8 mainframe OS and touring the National Cryptological Museum, in particular the USN versions of the machines used to break Engigma.

How I understand it, one of the main issues with breaking encryption like RSA is calculatind and testing large prime numbers as part of public key cryptography. Typically, this is done on a case by case basis, similar to dictionary attacks against passwords or using more complex analytics. The main issue is that this same effort is for each bit of cypher text presumably encrypted with a different key each time such as with ephemeral key cryptography. Like with brute force attacks against a password, constructing a rainbow table allows an attacker to spend more time preparing possible or probable hashes and clear text for a set of algorithms and character combinations.

With prime number or elliptic curve cryptography this gets harder as the values used are deliberately difficult to calculate. Finding an equation that predicts n prime numbers hasn't been found (to my knowledge) and there are highly computationally expensive calculations for elliptic curves. However, much of this has already been done, just not readily available. Similarly to rainbow tables, only having a dozen or even couple hundred keys wouldn't be very useful for trying to predict a curve or get a cohesive picture of what all 2048 through 4096 bit prime numbers are.

Given these challenges, computing a significant number of these keys would be a very expensive process in terms of hardware, power and physical space for the machines required to do this. Thankfully, such caring and generous corporations as Microsoft and Amazon freely give away cloud computing resources to the average joe. While one person is only supposed to have one trial account on Azure or one EC2 instance on AWS I think we can say that getting around this is fairly trivial for an attacker of reasonable sophistication. Or a lot of free time.

From there, scaling out an arbitrary number of VMs that exist only to crunch through RSA and ECDH keys could create a reasonably cohesive idea of what the keys are and what constitutes a valid key. Several million keys later, you have a good idea of what you're looking for an could start predicting probable values for these keys.

So far I'm about half a novel in and have yet to mention how mai nframes or batch processing plays into any of this. The main strength of mainframes is the massive I/O they have and the ability for running a frankly absurd number of virtual machines thanks to z/VM and LPARs, along with utilizing the I/O and resources in z/OS. Instead of trying to calculate the prime numbers in a 2048 or 4096 number, use the previously generated keys as well as generating every possible value between 4096 0s and 4096 1s, then divide the results by all nine counting numbers and keek whatever doesn't result in a nice, useful integer value. This won't get you the primes, but certainly cuts out a lot of chaff. From this point, the I/O capabilities of a mainframe come into play.

Having this sort of bandwidth and processing power means that it would be much faster to take the probable key values, run them through the algorithm and then see if the result has a certain threshold of dictionary words (for argument's sake, let's say 75% dictionary words), which could be sent on for human or AI review further along. At this point, you care less about being able to break one message with one key than being able to probably break any given message with some key.

While I don't think this is in any way a game changer (Has anyone seen the price of a new mainframe?) it could be an interesting concept and I'm sure others could improve upon it.

Included in my open source library. Has not been audited.

https://github.com/esaulpaugh/headlong/blob/master/src/main/java/com/joemelsha/crypto/hash/Keccak.java

Any good?

README

This community is currently set to restricted, so you may only browse. This will be changed soon.

Community Open For Posts.

I recommend you browse this subreddit using old reddit and install RES if you do not already have it. The layout is much better atleast on PCs.

About

This community is meant to be a cryptography-related community where crazy ideas, weird concepts, or creative solutions can be discussed. On top of this, other non-crypto related things that are useful for developers to know about can be talked about.

Audited Libraries

You are free to submit crypto libraries if you are experienced. I highly recommend they are programmed in Rust, to ensure memory safety and good performance, and use minimal dependencies.

You can create a rust library with:

cargo new <name> --lib

If you are looking for a Cryptographic Random Number Generator, I recommend you use the crate getrandom which is a cross-platform crate that retrieves random entropy from the OS Kernel instead of in Userspace.

Expanding On Ideas

This community is supposed to allow incomplete ideas or partially formed solutions to be examined by the general public, who may be able to help provide a solution to the problem. The point of this subreddit is to break down cryptography into more readable, understandable pieces, as opposed to reading 60 page long papers.

An example of a good break-down can be seen in the RFC for XMSS

Moderation

If you have experience with moderating or are well-involved with cryptography, feel free to PM me. If you feel that I made a mistake moderating, feel free again to either PM me or report me and I will try and address it.

Research

If you are interested in collaborating on research, you can PM me directly and talk about what research you are interested in.