Digital Signature Based on ISRSAC

Teng Yang,Yanshuo Zhang,Song Xiao,*,Yimin Zhao

1 Xidian University,Xi'an 710071,China

2 Beijing Electronic Science and Technology Institute,Beijing 100070,China

Abstract:Digital signature has recently played an increasingly important role in cyberspace security.Most of them are based on the public key cryptography.Public key cryptography is a mainstream cryptographic algorithm system that has been widely used in cyberspace security in recent years.The most classic public key cryptography algorithm is RSA and its difficulty is based on the large integer decomposition problem.In 2017,ISRSAC was proposed by M.Thangaval.ISRSAC has made security improvements to the RSA algorithm by increasing the complexity in factoring the value of modulus ‘n'.A digital signature algorithm based on ISRSAC algorithm was completed in this paper,and furthermore,a proxy signature algorithm based on ISRSAC and two kinds of multi-signature algorithms were presented,which include sequential multi-signature and broadcasting multi-signature.

Keywords:ISRSAC;digital signature;proxy signature;sequential multi-signature;broadcasting multisignature

I.INTRODUCTION

In 1976 Rivest,Shamir,and Adleman of the Massachusetts Institute of Technology proposed the RSA public-key cryptosystem,which opened a new door for cryptography[1,2].Its security is based on the problem of large integer factorization in number theory[3-6].On march 2018,Tangavel and Varalakshmi proposed an“Improved Secure RSA cryptosystem(ISRSAC) for Data Confidentiality in Cloud” [7].In their program,ISRSAC was proved to be more secure than RSA.

After the birth of the public key cryptosystem,digital signatures has been widely used in commercial communication systems such as electronic mail,electronic transfer,and office automation [1].Due to the integrity and non-repudiation of digital signatures,handwritten signatures are being replaced by digital signatures,and proxy signatures and multi-signatures are two types of this.

In real life,people often need to entrust some of their powers to reliable agents,so that agents can exercise these powers on their own behalf,including the right to sign in these delegated powers.The proxy signature is the original of the proxy signer.The signer generates a valid proxy signature.The recipient of the proxy signature verifies the proxy signature and the authorization information at the same time[8-15].In many cases,more than one person is required to sign a document.For example,a company's billing requires the signatures of the manager,the financial officer,and the cashier.Thus,a multi-signature of a document has been required[16-21].

In the previous,the digital signature system always based on the decomposition of large integers,most of them are based on RSA algorithm to make digital signatures,proxy signatures and multiple signatures.For example,the signature scheme of ZHANG [11]in 1997,the proxy signature scheme of LEE [12,13]in 2001,the scheme of Shun [14]in 2002,and the scheme of Tian [15]in 2015.In this article,digital signatures,proxy signatures,and multi-signature schemes are all based on the ISRSAC variant of the RSA algorithm,and its security is better than the digital signature based on RSA.

In this paper,the public key algorithm ISRSAC was introduced firstly,then proposed a digital signature scheme based on this,and extended it to proxy signature and multi-signature.The follow-up content of this article proves its theoretical correctness and feasibility,and conducts a comparative analysis to verify that its security is better than the digital signature based on RSA.

II.ISRSAC ALGORITHM

In this section,the ISRSAC algorithm will be introduced.RSA cryptosystem consists of three phases:prime key generation,encryption and decryption.The problem is that RSA is not secure against a brute force attack.The security of RSA cryptosystem depends on the large prime number because it is difficult to break.Hence a modified version of RSA for secure key generation is used to generate the public and private keys.The resulting algorithm is known as ISRSAC.To start the algorithm,we randomly choose two large primespandqwherep/=q,p ＞3,q ＞3,and find

An integerris randomly selected wherep ＞2r ＜q,which generate

Then a numbereis selected,which is satisfying 1＜e ＜α(n),where gcd(e,α(n))=1,then calculated,find

The public key pair is (e,n),and private key pair is(d,m).

Encryption:

SupposeMis plaintext message.We get ciphertextCby

Decryption:

We recovery message by:

III.DIGITAL SIGNATURE BASED ON ISRSAC

3.1 Key Generation

Choose two large primespandqwherep/=q,p ＞3,q ＞3,then generate

An integerris randomly selected wherep ＞2r ＜q,which find

Then a numbereis selected,which is satisfying 1＜e ＜α(n),wheregcd(e,α(n))=1,then calculated,find

(e,m)is public key of signer,(d,n)is private key of signer,Mis plaintext.

3.2 Signature Generation

The digital signature does not directly affect the plaintext.Generally speaking,the plaintext has a large character length,so it needs to be compressed before it is signed with a signature algorithm.The hash function compresses the information through a mathematical algorithm to obtain a summary of its information.The summary generated by the hash function will produce a fixed-length string output regardless of the length of the input information.The choice of hash algorithm should include the following characteristics:Firstly,given the plaintext and algorithm,the hash value can be calculated within a limited time and resources.Secondly,hash function should meet the condition of collision resistance.It means two different values get the same result after being hashed could not be found.Thirdly,it has the covertness,hash function must be irreversible.Considering the above points,the hash algorithm in this article selects the SM3 algorithm.SM3 is a hash algorithm independently developed by China,which perfectly meets the above requirements,and its security is equivalent to SHA-256.Thus SM3 was chosen as the hash function throughout this paper.

We know plaintextM,then select a hash functionh,calculateM′shash value ash(M).To sign theh(M),we use the private keydandn,then getSas the signature ofh(M)by

3.3 Signature Verification

To verify a signatureSon a messageM,first using the above hash function to calculate the hash valueh(M)of the plaintextM,then using the public keyeandmto verify whether the equation

is correct or not.If the equation is right,the signature is accepted.

3.4 Correctness Proof

The digital signature is based on ISRSAC,a public key cryptography,so the signature's proof is just like the proof on ISRSAC,the process is as follows:The signature verification is

From the last chapter,

From these two equations,

Assumek=(1/2r),

Substitute this equation in

By Fermat little therem,

IV.PROXY SIGNATURE SCHEME BASED ON ISRSAC

In real life work,people may not be able to personally sign certain documents for some reasons.However,the general digital signature does not have the function of proxy authorization.In order to solve this problem,the proxy signature system was presented.A complete proxy signature scheme consists of three participants:the original signature,the proxy signature and the signature verifier.The proxy signer obtains the signature right of the original signer,signs the message on his behalf,generates a proxy signature,and sends it to the verifier.The verifier receives the signature and then signs the validity and authorization of the signature.

4.1 Key Generation

Choose two large prime numbers p and q,then setn,m,α(n),eanddjust like ISRSAC.Then assume A as the original signer and B as the proxy signer.Based on the last chapter,the keys are as follows:

A:public keyeA,mA,private keydA,nA

B:public keyeB,mB,private keydB,nB

The message isM.

4.2 Authorization Process

When A intends to delegate the signing right to B,first selecting a hash functionh,calculatingM′shash value ash(M),then calculate

Then A sendSAandMto B.

Here the original signer's private keydAandnAis included in the authorization signatureSA,the proxy signer cannot get information aboutdAornAbased on the received authorization signature,and the proxy signer can only verify the authenticity of the signature based on the public key.

4.3 Authorization Verification

When B getSAandmfrom A,first use the same hash function to calculateh(M),then verify whether the equation

is correct or not.If the equation is right,then the trusted data source is reliable.

4.4 Proxy Signature Generation

When B haveSA,the following formula is used to generate a proxy signatureSB:

Then B sendSBandMto the acceptance party.

Here the authorization signatureSAis included in the proxy signatureSB,and the authorization signature is also included in the proxy signatureSB.The acceptance party can verify whether the agent is authorized and the authenticity of the proxy signature is based on the original signature party's public key and the proxy signature party's public key.

4.5 Proxy Signature Verification

When the acceptance party getMandSB,first calculateh(M) by using the same hash function,then use the public key of A and B to calculate

IfM′=h(M),the acceptance party receives B's proxy signature of the informationM.

V.DIGITAL MULTI-SIGNATURES SCHEMESBASED ON ISRSAC

Sometimes documents usually require multiple departments or departments to sign (or seal) separately to take effect.Multi-signature technology is a method to solve such problems in the network environment.The same document must pass through multiple people.Multi-signature colloquially refers to the participation of multiple signers in signing an electronic document.In simple terms,a multi-signature system answers questions such as who is participating in a signature,which order it is signed,which method is used to sign it,and how signatures and security can be verified.

5.1 Sequential Multi-signature

Sequential multi-signature is the signing and authentication of multiple users in the same order of the same message file.For example,in a company,there is a contract that requires the chairman,general manager,and department manager to sign together to be valid.The general manager only signs the contract after seeing the signature of the department manager.The chairman recognizes the general manager and the department manager.Based on the needs of similar scenarios,ordered multi-signature is also widely used.

5.1.1 System Establishment

Firstly,a power center needs to choose two large primespandqrandomly wherep /=q,p ＞3,q ＞3,then calculate

Then just like before,chooserande,findα(n) andd,after that,the power center set (e,n) as the public key and (d,m) as the private key.H(·) is a hash function,Uirepresents the signer,Mis the plaintext,IDi(i=(1,2,...,n) indicates the signer's identity and it is public.

In order to enable signerUito sign messageMproperly,the power center calculate

Distribute the certificate (IDi,Si) to each signerUithrough a secret secure channel,every signer use formulahi=Siemodmto verify the certificates(IDi,Si).

5.1.2 Partial Signature of the Message

Assuming that the order of signatures is (U1,U2,···,Un),each signer's identityIDi(i=1,2,···,n)and signature order needs to be published.

Step 1The signerU1chooser1(1＜r1＜n),then calculate

Step 2Send(K1,m1,D1)to the next signerU2,firstU2should verify the correctness of the signature:

Ifm1′=m1,this signature is accepted.When the partial signature is verified,U2complete its signature as follows:

Chooser2(1＜r2＜n)randomly and calculate

Send(K2,m2,D2,f1)to the next signerU3,and so on.

Step 3When signerUi(2＜i ＜n)send the partial signature (Ki,mi,Di,fi−1) of messageMto signerUi+1((fi−1)=fi−2hi−1mi−1),Ui+1should verify the correctness of the signature(Ki,mi,Di),the process is as follows:

Ifmi′=mi,this signature is accepted.Then the signerUi+1continue to signM:

Chooseri+1(1＜ri+1＜n)randomly and calculate

Send (Ki+1,mi+1,Di+1,fi) to the next signerUi+2until it is passed to the signerUn.Finally the signature ofMis(Kn,mn,Dn,fn−1).

5.1.3 Signature Verification

To verify the signature (Kn,mn,Dn,fn−1) on the messageM,calculate:

Ifmn′=mn,this signature is accepted.

5.2 Broadcasting Multi-signature

In many cases,many people need to sign the same file.For example,in an in-vehicle network,each on-board communication unit needs to sign the same event.In e-commerce,several agencies need to sign the same file.The signature required in the application scenario is multi-signature.Broadcast multi-signature is a form of multi-signature.Its characteristic is that each signature party passes its partial signature to the signature collector.The signature collector collects partial signatures and then performs verification.If all signatures are verified,then multiple signatures can be synthesized,otherwise do not assemble and synthesize them.

5.2.1 System Establishment

First,a power center needs to choose two large primespandqrandomly wherep /=q,p ＞3,q ＞3,then calculate

Then just like before,chooserande,findα(n) andd,after that,the power center set (e,n) as the public key and (d,m) as the private key.H(·) is a hash function,Uirepresents the signer,Mis the plaintext,IDi(i=(1,2,...,n) indicates the signer's identity and it is public.

Based on the same theory,we can finish a broadcasting multi-signature and Ur represents the receiver for the signature.

5.2.2 Signature Generation

Step 1Every signerUi(i=(1,2,...,n)chooserrandomly,calculate

Then sendRitoUr.

Step 2Urcalculate

Then broadcastK.

Step 3Every signerUicalculate

Then sendDitoUr.

5.2.3 Signature Verification

ReceiverUrcalculateD=D1·D2···Dn,finally the signature is(D,K,l).

When we want to verify the signature,calculate

Ifl=l′,this signature is accepted.

VI.EVALUATION

In this section,we compared and analyzed the scheme in this paper with the digital signature scheme based on RSA.Because the proxy signature adds a middleman to the digital signature and the multi-signature uses multiple public and private key pairs for multiple signatures,the security of both schemes depends on its core digital signature algorithm.Therefore,only the core digital signature algorithm needs to be analyzed in terms of security.

Figure1.Brute force attacks time comparison.

We performed brute force attacks on the scheme in this article and the digital signature scheme based on RSA(Figure1).Obviously,the scheme in this article requires more attack time than the scheme based on RSA,so the security of our scheme is better.As the length increases,the safety effect becomes much more significant.Therefore,the security of this scheme is far superior to that of digital signature scheme based on RSA.

VII.SUMMARY

In this paper,a digital signature scheme based on ISRSAC public key cryptography algorithm is given.Then a proxy digital signature scheme,an ordered multiple digital signature scheme and a broadcast multiple digital signature scheme are constructed.

ACKNOWLEDGEMENT

This work has been performed in National Natural Science Foundation of China (No.61772047,61372069),the Fundamental Research Funds for the Central Universities (No.328201902),National Defense Pre-research Foundation,SRF for ROCS,SEM(JY0600090102),111 project (No.B08038),and China Civil Aviation Information Technology Research Base Funded Project(CAAC-ITRB-201705).