Blind signature based on GOST 34.10-2001
Past and future elections is dedicated.
After stuffing, scandals, intrigues, investigations that were in the Duma elections, you unwittingly ask yourself: how to make sure everything is fair? Well, in relation to IT, how to make it so that everything is honest, and with the help of high technology? I read about hole punching and about QR codes , so I decided to make a modest mathematical contribution.
In this topic we will talk with you about how to solve two mutually opposite problems with the help of cryptography: the problem of voter verification and the problem of voting secrets. I will talk a little about the so-called “blind signature” and even present a demo application that shows how verification and anonymity tasks can be solved simultaneously, moreover, based on the GOST 34.10 and 34.11 cryptoalgorithms, which are officially approved by the FSB.
It is no secret to anyone that in civilized countries it has long been possible to vote in elections over the Internet. In this sense, the Estonian experience is indicative, with its cards and electronic signatures. The meaning of the Estonian system is that on election day a person signs his vote with his electronic signature conditionally (step 7). Meanwhile, in our country, where there is no trust in anyone and nothing, one necessarily has to admit that the scheme with simple user verification is no good, because in this case the secret of the expression of will may be violated theoretically. On the other hand, if you only care about the secrecy of the vote, then a situation may arise when the ballot box, or, in our case, the counter of ballots turns out to be superfluous with votes cast in favor of a certain party or a certain candidate, therefore the vote must be personalized.
The mechanism that we will consider at the same time protects the privacy of a given vote, and unequivocally verifies the voter. This is achieved with the help of the so-called "blind" electronic signature. The problem solved with the help of a blind signature can be formulated in two sentences like this:
')
Now about the mechanism. The one who will verify our identity (let's call him a validator) should not know who we voted for on the ballot. And the one who considers our newsletter (and we will call him the counter), should not know our identity. Consequently, our messages to the validator and the counter should differ from each other, moreover, so that the validator and the counter, by agreement, could not determine which bulletin belongs to whom. But on the other hand, if the counter trusts the signature of the validator, then the validator receives information from us that is identical to the information that the counter receives, right?
Of course, yes, not so. Let me explain by example. Suppose a validator signs a message by multiplying it by 2, i.e. we send the number to the validator, it returns us the doubled number as a signature and the counter recognizes the signature as true. We send the validator 1, it returns 2 to us, we send a pair of 1 and 2 to the counter, the counter looks that yes, indeed, 2 is exactly 2 times more than 1 and recognizes the signature to be true. And now we do it differently, we take our message (1), send a double message to the validator (2), he signs it, returns the signature (4), we perform the inverse transformation, divide the four by two, we get the true signature (2) for our messages. Thus, the validator did not know our message (how did he know by how much the message was multiplied? By two? Or maybe by two?), But from his signature of our disguised message we restored the true signature for our secret message.
Now let's talk a little bit about the algorithm GOST R 34.10-2001. This algorithm was adopted instead of the GOST 34.10-94 algorithm, and here even the differences are briefly described. The algorithm differs from the well-known RSA by a complicated problem, if RSA uses the complex problem of factoring a number, then GOST R 34.10-2001 is based on elliptic curves and uses the problem of calculating the discrete logarithm in a group of points. Between us, girls, speaking, elliptic curves are very interesting things and are not fully understood. This is a fairly new area of ​​mathematics, which opens up broad perspectives. Is it worth mentioning that the proof of Fermat's Great Theorem was based precisely on elliptic curves?
How GOST works (let me just write GOST instead of GOST R 34.10-2001), you can find out by dropping to the sixth page of the standard , and below is the present with a modified algorithm:
Thus, we get the general scheme:
If necessary, the voter can, by his unique identifying line, check for which of the parties his vote was counted. The role of observers in such elections is reduced to two places: observation of the validator so that he does not distribute signatures to disguised hashes signed by anyone, and observation of the counter so that he does not wind up when receiving ballots signed incorrectly.
And finally, my demo is an application on C #, which blindly signs GOST 34.11-hash of the word "Bulletin". The buttons are pressed sequentially, after each pressing they take data from the controls, nothing is stored in the memory except the curve parameters. The curve itself is taken in the original GOST, but, of course, if you wish, you can replace it with one of the CryptoProssers. Red is what is secret, blue is what is being sent. I used the BouncyCastle cryptographic libraries to generate a key pair and verify the signature, while the very signature of the “blind” signature occurs directly within the program.
The source application can be collected here .
In conclusion, I’ll note that even now the law allows the use of an electronic signature along with a handwritten one, therefore validation of a voter is possible even now. And also a special thank you to Professor N.A. Moldavian for an article in International Journal of Network Security last May.
After stuffing, scandals, intrigues, investigations that were in the Duma elections, you unwittingly ask yourself: how to make sure everything is fair? Well, in relation to IT, how to make it so that everything is honest, and with the help of high technology? I read about hole punching and about QR codes , so I decided to make a modest mathematical contribution.
In this topic we will talk with you about how to solve two mutually opposite problems with the help of cryptography: the problem of voter verification and the problem of voting secrets. I will talk a little about the so-called “blind signature” and even present a demo application that shows how verification and anonymity tasks can be solved simultaneously, moreover, based on the GOST 34.10 and 34.11 cryptoalgorithms, which are officially approved by the FSB.
It is no secret to anyone that in civilized countries it has long been possible to vote in elections over the Internet. In this sense, the Estonian experience is indicative, with its cards and electronic signatures. The meaning of the Estonian system is that on election day a person signs his vote with his electronic signature conditionally (step 7). Meanwhile, in our country, where there is no trust in anyone and nothing, one necessarily has to admit that the scheme with simple user verification is no good, because in this case the secret of the expression of will may be violated theoretically. On the other hand, if you only care about the secrecy of the vote, then a situation may arise when the ballot box, or, in our case, the counter of ballots turns out to be superfluous with votes cast in favor of a certain party or a certain candidate, therefore the vote must be personalized.
Blind signature
The mechanism that we will consider at the same time protects the privacy of a given vote, and unequivocally verifies the voter. This is achieved with the help of the so-called "blind" electronic signature. The problem solved with the help of a blind signature can be formulated in two sentences like this:
- Alice wants to anonymously send some reliable information to Caesar;
- Bob can certify the source of information (Alice), but should not know its essence.
- Alice seals a piece of information in an envelope;
- Alice brings a sealed envelope to Bob;
- Bob sees that Alice is Alice and puts a stamp on the envelope with the information, without seeing its essence;
- Alice goes to the post office and sends an envelope with a stamp to Caesar without a return address;
- Caesar receives an envelope, sees the stamp of Bob and trusts the source of information without knowing this source.
')
Mechanism
Now about the mechanism. The one who will verify our identity (let's call him a validator) should not know who we voted for on the ballot. And the one who considers our newsletter (and we will call him the counter), should not know our identity. Consequently, our messages to the validator and the counter should differ from each other, moreover, so that the validator and the counter, by agreement, could not determine which bulletin belongs to whom. But on the other hand, if the counter trusts the signature of the validator, then the validator receives information from us that is identical to the information that the counter receives, right?
Of course, yes, not so. Let me explain by example. Suppose a validator signs a message by multiplying it by 2, i.e. we send the number to the validator, it returns us the doubled number as a signature and the counter recognizes the signature as true. We send the validator 1, it returns 2 to us, we send a pair of 1 and 2 to the counter, the counter looks that yes, indeed, 2 is exactly 2 times more than 1 and recognizes the signature to be true. And now we do it differently, we take our message (1), send a double message to the validator (2), he signs it, returns the signature (4), we perform the inverse transformation, divide the four by two, we get the true signature (2) for our messages. Thus, the validator did not know our message (how did he know by how much the message was multiplied? By two? Or maybe by two?), But from his signature of our disguised message we restored the true signature for our secret message.
Standard
Now let's talk a little bit about the algorithm GOST R 34.10-2001. This algorithm was adopted instead of the GOST 34.10-94 algorithm, and here even the differences are briefly described. The algorithm differs from the well-known RSA by a complicated problem, if RSA uses the complex problem of factoring a number, then GOST R 34.10-2001 is based on elliptic curves and uses the problem of calculating the discrete logarithm in a group of points. Between us, girls, speaking, elliptic curves are very interesting things and are not fully understood. This is a fairly new area of ​​mathematics, which opens up broad perspectives. Is it worth mentioning that the proof of Fermat's Great Theorem was based precisely on elliptic curves?
How GOST works (let me just write GOST instead of GOST R 34.10-2001), you can find out by dropping to the sixth page of the standard , and below is the present with a modified algorithm:
Voting
Thus, we get the general scheme:
- The voter establishes a secure connection with the validator. Protected in the sense that, firstly, the voter knows for sure that the validator is a validator (no one has yet canceled SSL), and the validator knows for sure that the voter is a voter (just the outgoing data stream the voter signs with his private key);
- The voter generates a ballot paper, votes for any other party, adds a unique sequence of characters to the ballot and hashes the ballot;
- The voter adds a masking factor to the hash of the bulletin and sends it to the validator for signature;
- The validator checks if this voter has already voted. In the case of a negative check, sign a masked hash;
- The voter extracts a masking factor from the signature and obtains a valid signature for his original hash of the bulletin;
- The voter establishes an unprotected open connection with the counter from any place that he considers anonymous (although, for example, he registers the address on mail.ru and sends it by registered mail) and sends the signed bulletin.
- The counter checks the correctness of the signature of the bulletin, the uniqueness of the identifier, if the check is positive, appends the +1 vote of any other party.
If necessary, the voter can, by his unique identifying line, check for which of the parties his vote was counted. The role of observers in such elections is reduced to two places: observation of the validator so that he does not distribute signatures to disguised hashes signed by anyone, and observation of the counter so that he does not wind up when receiving ballots signed incorrectly.
application
And finally, my demo is an application on C #, which blindly signs GOST 34.11-hash of the word "Bulletin". The buttons are pressed sequentially, after each pressing they take data from the controls, nothing is stored in the memory except the curve parameters. The curve itself is taken in the original GOST, but, of course, if you wish, you can replace it with one of the CryptoProssers. Red is what is secret, blue is what is being sent. I used the BouncyCastle cryptographic libraries to generate a key pair and verify the signature, while the very signature of the “blind” signature occurs directly within the program.
The source application can be collected here .
In conclusion, I’ll note that even now the law allows the use of an electronic signature along with a handwritten one, therefore validation of a voter is possible even now. And also a special thank you to Professor N.A. Moldavian for an article in International Journal of Network Security last May.
Source: https://habr.com/ru/post/136022/
All Articles