Lamport signature
ક્રિપ્ટોગ્રાફીમાં, લેમ્પોર્ટ સિગ્નેચર અથવા લેમ્પોર્ટ વન-ટાઇમ સિગ્નેચર સ્કીમ એ ડિજિટલ સિગ્નેચર બનાવવાની એક પદ્ધતિ છે. લેમ્પોર્ટ સિગ્નેચર કોઈપણ ક્રિપ્ટોગ્રાફિકલી સુરક્ષિત વન-વે ફંક્શનમાંથી બનાવી શકાય છે; સામાન્ય રીતે ક્રિપ્ટોગ્રાફિક હેશ ફંક્શનનો ઉપયોગ થાય છે. જોકે ક્વોન્ટમ કમ્પ્યુટર્સના સંભવિત વિકાસથી આર. એસ. એ. જેવા સંકેતલિપીના ઘણા સામાન્ય સ્વરૂપોની સુરક્ષાને ખતરો છે, એવું માનવામાં આવે છે કે મોટા હેશ કાર્યો સાથે લેમ્પોર્ટ સહીઓ હજુ પણ તે ઘટનામાં સુરક્ષિત રહેશે. દરેક લેમ્પોર્ટ કીનો ઉપયોગ માત્ર એક જ સંદેશ પર સહી કરવા માટે થઈ શકે છે. જો કે, ઘણા લેમ્પોર્ટ સહીઓને એક મર્કલ હેશ ટ્રી દ્વારા નિયંત્રિત કરી શકાય છે, આમ ઘણા સંદેશાઓ માટે એક જ હેશ ટ્રી કીનો ઉપયોગ કરી શકાય છે, જે આને એકદમ કાર્યક્ષમ ડિજિટલ હસ્તાક્ષર યોજના બનાવે છે. લેમ્પોર્ટ સિગ્નેચર ક્રિપ્ટોસિસ્ટમની શોધ 1979માં કરવામાં આવી હતી અને તેનું નામ તેના શોધક લેસ્લી લેમ્પોર્ટના નામ પરથી રાખવામાં આવ્યું હતું. ઉદાહરણ એલિસ પાસે 256-બીટ ક્રિપ્ટોગ્રાફિક હેશ ફંક્શન અને અમુક પ્રકારનું સુરક્ષિત રેન્ડમ નંબર જનરેટર છે. તે લેમ્પોર્ટ કી જોડી, એટલે કે ખાનગી કી અને અનુરૂપ જાહેર કી બનાવવા અને તેનો ઉપયોગ કરવા માંગે છે. ખાનગી કી બનાવવા માટે એલિસ રેન્ડમ નંબર જનરેટરનો ઉપયોગ 256 જોડી રેન્ડમ સંખ્યાઓ (કુલ 2 × 256 સંખ્યાઓ) બનાવવા માટે કરે છે, દરેક સંખ્યા કદમાં 256 બિટ્સ હોય છે, એટલે કે કુલ 2 × 256 × 256 બિટ્સ = કુલ 128 કિબિટ. આ તેની ખાનગી ચાવી છે અને તે તેને પછીના ઉપયોગ માટે સુરક્ષિત જગ્યાએ સંગ્રહિત કરશે. જાહેર કી બનાવવા માટે તે ખાનગી કીમાં 512 રેન્ડમ નંબરોમાંથી દરેકને હેશ કરે છે, આમ 512 હેશ બનાવે છે, દરેક કદમાં 256 બિટ્સ. (કુલ 128 કેબિટ પણ.) આ 512 હેશ તેમની સાર્વજનિક ચાવી બનાવે છે, જે તેઓ દુનિયા સાથે શેર કરશે. પછીના સંદેશ પર સહી કરીને એલિસ સંદેશ પર સહી કરવા માંગે છે. પહેલા તે સંદેશને 256-બીટ હેશ રકમ પર હેશ કરે છે. પછી, હેશમાં દરેક બીટ માટે, બીટની કિંમતના આધારે, તે સંખ્યાઓની અનુરૂપ જોડીમાંથી એક નંબર પસંદ કરે છે જે તેની ખાનગી કી બનાવે છે (એટલે કે, જો બીટ 0 હોય, તો પ્રથમ નંબર પસંદ કરવામાં આવે છે, અને જો બીટ 1 હોય, તો બીજો પસંદ કરવામાં આવે છે). આ 256 સંખ્યાઓનો ક્રમ ઉત્પન્ન કરે છે. દરેક સંખ્યા પોતે 256 બિટ્સ લાંબી હોવાથી તેના હસ્તાક્ષરનું કુલ કદ 256 × 256 બિટ્સ = 65536 બિટ્સ = 64 કિબિટ હશે. આ (મૂળ રૂપે યાદૃચ્છિક રીતે પસંદ કરેલા) નંબરો તેમની સહી છે અને તેઓ તેમને સંદેશ સાથે પ્રકાશિત કરે છે. નોંધ લો કે હવે જ્યારે એલિસની ખાનગી કીનો ઉપયોગ કરવામાં આવ્યો છે, ત્યારે તેનો ફરીથી ક્યારેય ઉપયોગ થવો જોઈએ નહીં. તેણે અન્ય 256 નંબરોનો નાશ કરવો પડશે જેનો તેણે સહી માટે ઉપયોગ કર્યો ન હતો. નહિંતર, ખાનગી કીનો ફરીથી ઉપયોગ કરતી દરેક વધારાની સહી વિરોધીઓ સામે સુરક્ષા સ્તરને ઘટાડે છે જે પછીથી તેમની ખોટી સહીઓ બનાવી શકે છે. સહીની ચકાસણી પછી બોબ સંદેશની એલિસની સહી ચકાસવા માંગે છે. તે 256-બીટ હેશ રકમ મેળવવા માટે સંદેશ પણ હેશ કરે છે. પછી તે એલિસની પબ્લિક કીમાં 256 હેશ પસંદ કરવા માટે હેશ રકમના બિટ્સનો ઉપયોગ કરે છે. તે એ જ રીતે હેશ પસંદ કરે છે જે રીતે એલિસે સહી માટે રેન્ડમ નંબરો પસંદ કર્યા હતા. એટલે કે, જો સંદેશ હેશનો પ્રથમ બીટ 0 હોય, તો તે પ્રથમ જોડીમાં પ્રથમ હેશ પસંદ કરે છે, વગેરે. પછી બોબ એલિસની સહીમાં 256 રેન્ડમ નંબરોમાંથી દરેકને હેશ કરે છે. આ તેને 256 હેશ આપે છે. જો આ 256 હેશ એલિસની પબ્લિક કીમાંથી તેણે હમણાં જ પસંદ કરેલી 256 હેશ સાથે બરાબર મેળ ખાય તો સહી બરાબર છે. જો નહીં, તો સહી ખોટી છે. નોંધ લો કે એલિસ સંદેશની સહી પ્રકાશિત કરે તે પહેલાં, ખાનગી કીમાં 2 × 256 રેન્ડમ નંબરો અન્ય કોઈ જાણતું નથી. આમ, હસ્તાક્ષર માટે 256 યાદૃચ્છિક સંખ્યાઓની યોગ્ય સૂચિ અન્ય કોઈ બનાવી શકતું નથી. અને એલિસે સહી પ્રકાશિત કર્યા પછી, અન્ય લોકો હજુ પણ અન્ય 256 રેન્ડમ નંબરોને જાણતા નથી અને આમ અન્ય સંદેશ હેશમાં બંધબેસતા સહીઓ બનાવી શકતા નથી. ઔપચારિક વર્ણન નીચે લેમ્પોર્ટ સહીઓ કેવી રીતે કાર્ય કરે છે તેનું ટૂંકું વર્ણન છે, જે ગાણિતિક સંકેતલિપીમાં લખાયેલું છે. નોંધ લો કે આ વર્ણનમાં "સંદેશ" એ વાજબી કદનો એક નિશ્ચિત કદનો બ્લોક છે, સંભવતઃ (પરંતુ જરૂરી નથી) મનસ્વી રીતે લાંબા સંદેશ પર હસ્તાક્ષર કરવામાં આવતા હેશનું પરિણામ છે. કીઓ હકારાત્મક પૂર્ણાંક હોવો જોઈએ અને સંદેશાઓનો સમૂહ હોવો જોઈએ. ચાલો એક તરફી કાર્ય બનીએ. માટે અને સહી કરનાર અવ્યવસ્થિત રીતે પસંદ કરે છે અને ગણતરી કરે છે. ખાનગી કી, મૂલ્યો ધરાવે છે. સાર્વજનિક કીમાં મૂલ્યોનો સમાવેશ થાય છે. સંદેશ પર સહી કરવી એ એક સંદેશ હોવો જોઈએ. સંદેશની સહી છે. સહીની ચકાસણી ચકાસણી કરનાર તે તમામ માટે ચકાસીને સહીને માન્ય કરે છે. સંદેશને બનાવટી બનાવવા માટે ઈવેએ એક તરફી કાર્યને ઉલટાવવું પડશે. યોગ્ય કદના ઇનપુટ્સ અને આઉટપુટ માટે આ અવ્યવહારુ હોવાનું માનવામાં આવે છે. સુરક્ષા પરિમાણો લેમ્પોર્ટ સહીઓની સુરક્ષા વન-વે હેશ કાર્યની સુરક્ષા અને તેના આઉટપુટની લંબાઈ પર આધારિત છે. એન-બીટ મેસેજ ડાયજેસ્ટ જનરેટ કરતા હેશ ફંક્શન માટે, એક જ હેશ ફંક્શનના આહ્વાન પર આદર્શ પ્રિમેજ અને બીજો પ્રિમેજ પ્રતિકાર ક્લાસિકલ કમ્પ્યુટિંગ મોડેલ હેઠળ અથડામણ શોધવા માટે 2n કામગીરીના ક્રમ પર સૂચવે છે. ગ્રોવરના અલ્ગોરિધમ મુજબ, આદર્શ હેશ ફંક્શનના એક જ આહ્વાન પર પૂર્વ-છબી અથડામણ શોધવી એ ક્વોન્ટમ કમ્પ્યુટિંગ મોડેલ હેઠળ O (2n/2) કામગીરી પર ઉપલા બંધાયેલ છે. લેમ્પોર્ટ સહીઓમાં, જાહેર કી અને સહીનો દરેક ભાગ ટૂંકા સંદેશાઓ પર આધારિત હોય છે જેમાં હેશ કાર્ય માટે માત્ર એક જ આહ્વાનની જરૂર હોય છે. દરેક ખાનગી કી yi, j અને તેની અનુરૂપ ઝી, જે જાહેર કી જોડી માટે, ખાનગી કી લંબાઈ પસંદ કરવી આવશ્યક છે જેથી ઇનપુટની લંબાઈ પર પ્રિમેજ હુમલો કરવો એ આઉટપુટની લંબાઈ પર પ્રિમેજ હુમલો કરવા કરતાં ઝડપી નથી. ઉદાહરણ તરીકે, અધોગતિના કિસ્સામાં, જો દરેક ખાનગી કી yi, j તત્વની લંબાઈ માત્ર 16 બિટ્સ હોય, તો સંદેશની ડાયજેસ્ટ લંબાઈને ધ્યાનમાં લીધા વિના, આઉટપુટ સાથે મેળ શોધવા માટે 216 કામગીરીઓમાં તમામ 216 સંભવિત ખાનગી કી સંયોજનોને સંપૂર્ણ રીતે શોધવું તુચ્છ છે. તેથી, સંતુલિત પ્રણાલી રચના એ સુનિશ્ચિત કરે છે કે બંને લંબાઈ લગભગ સમાન હોય. ગ્રોવરના અલ્ગોરિધમ પર આધારિત, ક્વોન્ટમ સિક્યોર સિસ્ટમ, પબ્લિક કી એલિમેન્ટ્સ ઝી, જે, પ્રાઇવેટ કી એલિમેન્ટ્સ યી, જે અને સિગ્નેચર એલિમેન્ટ્સ સી, જે ની લંબાઈ સિસ્ટમના સિક્યુરિટી રેટિંગ કરતા ઓછામાં ઓછી 2 ગણી મોટી હોવી જોઈએ. એટલે કેઃ 80-બીટ સુરક્ષિત સિસ્ટમ 160 બીટથી ઓછી ન હોય તેવી તત્વ લંબાઈનો ઉપયોગ કરે છે; 128-બીટ સુરક્ષિત સિસ્ટમ 256 બીટથી ઓછી ન હોય તેવી તત્વ લંબાઈનો ઉપયોગ કરે છે; જો કે સાવચેતી રાખવી જોઈએ કારણ કે ઉપરના આદર્શવાદી કાર્ય અંદાજો એક આદર્શ (સંપૂર્ણ) હેશ કાર્યને ધારે છે અને તે હુમલાઓ સુધી મર્યાદિત છે જે એક સમયે માત્ર એક જ પૂર્વચિત્રને લક્ષ્ય બનાવે છે. તે પરંપરાગત કમ્પ્યુટિંગ મોડેલ હેઠળ જાણીતું છે કે જો 23n/5 પૂર્વચિત્રો શોધવામાં આવે, તો પૂર્વચિત્ર દીઠ સંપૂર્ણ કિંમત 2n/2 થી ઘટીને 22n/5 થઈ જાય છે. બહુવિધ સંદેશ પાચનના સંગ્રહને ધ્યાનમાં રાખીને મહત્તમ ઘટક કદ પસંદ કરવું એ એક ખુલ્લી સમસ્યા છે. મોટા તત્વ કદ અને મજબૂત હેશ કાર્યોની પસંદગી, જેમ કે 512-બીટ ઘટકો અને SHA-512, આ અજ્ઞાતનું સંચાલન કરવા માટે વધુ સુરક્ષા માર્જિન સુનિશ્ચિત કરે છે. ઓપ્ટિમાઇઝેશન અને વેરિયન્ટ્સ ટૂંકી ખાનગી કી ખાનગી કીની તમામ રેન્ડમ સંખ્યાઓ બનાવવા અને સંગ્રહિત કરવાને બદલે, પૂરતા કદની એક જ કી સંગ્રહિત કરી શકાય છે. (સામાન્ય રીતે ખાનગી કીમાં રેન્ડમ સંખ્યાઓમાંથી એક જેટલું જ કદ.) જ્યારે જરૂર પડે ત્યારે ખાનગી કીમાં તમામ રેન્ડમ સંખ્યાઓ બનાવવા માટે એક જ કીનો ઉપયોગ ક્રિપ્ટોગ્રાફિકલી સુરક્ષિત સ્યુડોરાન્ડમ નંબર જનરેટર (સી. એસ. પી. આર. એન. જી.) માટે બીજ તરીકે થઈ શકે છે. નોંધ લો કે ક્રિપ્ટોગ્રાફિકલી સુરક્ષિત હેશ (અથવા ઓછામાં ઓછું જેનું આઉટપુટ બીજ સાથે XOR નથી) નો ઉપયોગ CSPRNG ને બદલે કરી શકાતો નથી કારણ કે સંદેશ પર હસ્તાક્ષર કરવાથી ખાનગી કીમાંથી વધારાના રેન્ડમ મૂલ્યો જાહેર થશે. જો વિરોધી ઇચ્છિત પ્રાપ્તકર્તા કરી શકે તે પહેલાં સહી કરી શકે છે, તો તે ખાનગી કીમાંથી જાહેર થયેલ રેન્ડમ મૂલ્યોના દરેક બમણા માટે સુરક્ષા સ્તરના અડધા સાથે હસ્તાક્ષર કરી શકે છે. એ જ રીતે ઘણી લેમ્પોર્ટ કીઓ બનાવવા માટે CSPRNG સાથે એક જ કીનો ઉપયોગ કરી શકાય છે. પ્રાધાન્યમાં પછી અમુક પ્રકારની પોસ્ટ-ક્વોન્ટમ સુરક્ષિત રેન્ડમ એક્સેસ CSPRNG નો ઉપયોગ કરવો જોઈએ. નોંધપાત્ર રીતે, બીબીએસ જેવા ક્લાસિક સી. એસ. પી. આર. એન. જી. નો ઉપયોગ કરવો જોઈએ નહીં. ટૂંકી જાહેર કી એ લેમ્પોર્ટ સહીને હેશ સૂચિ સાથે જોડી શકાય છે, જેનાથી જાહેર કીમાં તમામ હેશને બદલે માત્ર એક જ ટોપ હેશને પ્રકાશિત કરવાનું શક્ય બને છે. એટલે કે મૂલ્યોને બદલે. સિંગલ ટોપ હેશ સામે ચકાસવા માટે, સહીમાં જાહેર કીની હેશ સૂચિમાંથી રેન્ડમ નંબરો અને બિનઉપયોગી હેશનો સમાવેશ થવો આવશ્યક છે, જેના પરિણામે લગભગ બમણા કદની સહીઓ થાય છે. એટલે કે, બધા માટેના મૂલ્યોનો સમાવેશ કરવાની જરૂર છે. જો હેશ લિસ્ટને બદલે ક્રિપ્ટોગ્રાફિક એક્યુમ્યુલેટરનો ઉપયોગ કરવામાં આવે તો બિનઉપયોગી હેશને સહીમાં સામેલ કરવાની જરૂર નથી. ટૂંકી કીઓ અને સહી વિન્ટરનિટ્ઝ હસ્તાક્ષર સંકોચન ખાનગી કી અને જાહેર કીનું કદ ઘટાડે છે, અને હસ્તાક્ષર માટેના અડધા પરિબળ કરતાં સહેજ ઓછું કરે છે. ગણતરી એક પરિબળ કરતાં સહેજ વધારે વધે છે. સી. એસ. પી. આર. એન. જી. ની જરૂરિયાતને બદલે ક્રિપ્ટોગ્રાફિકલી સુરક્ષિત હેશ પૂરતું છે. અગાઉના વિભાગમાં સમજાવ્યા મુજબ સહીના કદને બમણી કરવાના ખર્ચે જાહેર કીને એક જ મૂલ્ય સુધી ટૂંકી કરવા માટે પણ હેશ લિસ્ટનો ઉપયોગ કરી શકાય છે. બહુવિધ સંદેશાઓ માટે સાર્વજનિક કી દરેક લેમ્પોર્ટ સાર્વજનિક કીનો ઉપયોગ ફક્ત એક જ સંદેશ પર સહી કરવા માટે થઈ શકે છે, જેનો અર્થ છે કે જો ઘણા સંદેશાઓ પર સહી કરવાની હોય તો ઘણી કીઓ પ્રકાશિત કરવી પડે છે. પરંતુ તે જાહેર કીઓ પર હેશ ટ્રીનો ઉપયોગ કરી શકાય છે, તેના બદલે હેશ ટ્રીની ટોચની હેશને પ્રકાશિત કરી શકાય છે. આનાથી પરિણામી સહીનું કદ વધે છે, કારણ કે હેશ ટ્રીની એક શાખાને સહીમાં શામેલ કરવી પડે છે, પરંતુ તે એક જ હેશને પ્રકાશિત કરવાનું શક્ય બનાવે છે જેનો ઉપયોગ પછી મોટી સંખ્યામાં ભાવિ સહીઓને ચકાસવા માટે થઈ શકે છે. એસ/કી સંદર્ભો વધુ વાંચન એલ. લેમ્પોર્ટ, કન્સ્ટ્રક્ટિંગ ડિજિટલ સિગ્નેચર ફ્રોમ એ વન-વે ફંક્શન, ટેકનિકલ રિપોર્ટ એસઆરઆઈ-સીએસએલ-98, એસઆરઆઈ ઇન્ટરનેશનલ કમ્પ્યુટર સાયન્સ લેબોરેટરી, ઓક્ટોબર 1979 જુઓ. મર્કલ વૃક્ષોનો કાર્યક્ષમ ઉપયોગ-આર. એસ. એ. પ્રયોગશાળાઓ મર્કલ વૃક્ષો + લેમ્પોર્ટ સિગ્નેચરના મૂળ હેતુની સમજ, એક કાર્યક્ષમ વન-ટાઇમ સિગ્નેચર યોજના તરીકે. એડમ લેંગલી દ્વારા હેશ-આધારિત સહીઓ અને મર્કલ સહીઓનો પરિચય. બ્લેક2બી (સી + +) ની ટોચ પર લેમ્પોર્ટ યોજનાનું સંદર્ભ અમલીકરણ સંદર્ભ SHA256, SHA512, અથવા બ્લેક2બી (રસ્ટ) ની ટોચ પર લેમ્પોર્ટ હસ્તાક્ષરોનું અમલીકરણ ડિજિટલ હસ્તાક્ષર યોજનાઓ હેશ-આધારિત સંકેતલિપી