Coppersmith's attack
કોપરસ્મિથના હુમલામાં કોપરસ્મિથ પદ્ધતિ પર આધારિત જાહેર-કી ક્રિપ્ટોસિસ્ટમ આરએસએ પર ક્રિપ્ટોગ્રાફિક હુમલાના વર્ગનું વર્ણન કરવામાં આવ્યું છે. આરએસએ પર હુમલો કરવા માટે કોપરસ્મિથ પદ્ધતિની ખાસ એપ્લિકેશનોમાં એવા કિસ્સાઓનો સમાવેશ થાય છે જ્યારે જાહેર ઘાતાંક ઇ નાનો હોય અથવા જ્યારે ગુપ્ત કીના મુખ્ય પરિબળનું આંશિક જ્ઞાન ઉપલબ્ધ હોય. આર. એસ. એ. ની મૂળભૂત બાબતો આર. એસ. એ. પ્રણાલીમાં જાહેર કી એ પૂર્ણાંકોનું ટુપલ છે, જ્યાં એન એ બે અવિભાજ્ય સંખ્યાઓ p અને q નું ગુણાકાર છે. ગુપ્ત કી પૂર્ણાંક d સંતોષકારક દ્વારા આપવામાં આવે છે; સમાનરૂપે, ગુપ્ત કી દ્વારા આપવામાં આવી શકે છે અને જો ચીની શેષ પ્રમેયનો ઉપયોગ ડિક્રિપ્શનની ગતિ સુધારવા માટે કરવામાં આવે છે, તો જુઓ CRT-RSA. સંદેશ M નું એન્ક્રિપ્શન સિફરટેક્સ્ટ ઉત્પન્ન કરે છે, જેને કમ્પ્યુટિંગ દ્વારા ડિક્રિપ્ટ કરી શકાય છે. લો પબ્લિક એક્સ્પોનન્ટ એટેક એન્ક્રિપ્શન અથવા સહી ચકાસણીના સમયને ઘટાડવા માટે, નાના પબ્લિક એક્સ્પોનન્ટ () નો ઉપયોગ કરવો ઉપયોગી છે. વ્યવહારમાં, 3,17 અને 65537 માટે સામાન્ય પસંદગીઓ છે. e માટે આ મૂલ્યો ફર્મેટ પ્રાઈમ છે, જેને કેટલીકવાર અનુક્રમે તરીકે ઓળખવામાં આવે છે. તેઓ પસંદ કરવામાં આવે છે કારણ કે તેઓ મોડ્યુલર એક્સ્પોનેન્શિયેશન ઓપરેશનને ઝડપી બનાવે છે. ઉપરાંત, આવી પસંદગી કર્યા પછી, કી જનરેશનના પગલું 1 માં પ્રાઇમ જનરેટ કરતી વખતે અને તેનું પરીક્ષણ કરતી વખતે તે ચકાસવું સરળ છે. આ પરીક્ષણના મૂલ્યો કે જે નિષ્ફળ જાય છે તેને ત્યાં અને પછી નકારી શકાય છે. (વધુ સારુંઃ જો e એ અવિભાજ્ય અને 2 કરતા વધારે હોય, તો પરીક્ષણ વધુ ખર્ચાળ પરીક્ષણને બદલી શકે છે.) જો પબ્લિક એક્સપોનેન્ટ નાનો હોય અને પ્લેનટેક્સ્ટ ખૂબ જ ટૂંકો હોય, તો RSA ફંક્શનને ઉલટાવવું સરળ હોઈ શકે છે, જે ચોક્કસ હુમલાઓને શક્ય બનાવે છે. પેડિંગ યોજનાઓ એ સુનિશ્ચિત કરે છે કે સંદેશાઓની સંપૂર્ણ લંબાઈ હોય, પરંતુ વધુમાં જાહેર સૂચક પસંદ કરવાની ભલામણ કરવામાં આવે છે. જ્યારે આ મૂલ્યનો ઉપયોગ કરવામાં આવે છે, ત્યારે હસ્તાક્ષર ચકાસણી માટે 17 ગુણાકારની જરૂર પડે છે, જ્યારે સમાન કદના રેન્ડમનો ઉપયોગ કરવામાં આવે ત્યારે લગભગ 25 ની સરખામણીમાં. લો પ્રાઇવેટ એક્સ્પોનન્ટથી વિપરીત (જુઓ વીનરનો હુમલો), જ્યારે નાનો ઉપયોગ કરવામાં આવે ત્યારે લાગુ થતા હુમલાઓ કુલ વિરામથી દૂર હોય છે, જે ગુપ્ત કીને પુનઃપ્રાપ્ત કરશે. કોપરસ્મિથ પદ્ધતિ પ્રમેય 1 (કોપરસ્મિથ) ધારો કે N એક પૂર્ણાંક છે અને પૂર્ણાંકો પર ડિગ્રીની મોનિક બહુપદી છે. માટે સુયોજિત કરો. પછી, આપેલ, હુમલાખોર (ઇવ) તમામ પૂર્ણાંકોને અસરકારક રીતે સંતોષકારક શોધી શકે છે. ચાલી રહેલો સમય LLL અલ્ગોરિધમને પરિમાણ O ની જાળી પર ચલાવવામાં લાગતા સમય દ્વારા પ્રભુત્વ ધરાવે છે. આ પ્રમેય એક અલ્ગોરિધમનો અસ્તિત્વ દર્શાવે છે જે તેના કરતા નાના મોડ્યુલોના તમામ મૂળને અસરકારક રીતે શોધી શકે છે. જેમ જેમ નાનું થતું જાય છે તેમ તેમ અલ્ગોરિધમનો રનટાઇમ ઘટતો જાય છે. આ પ્રમેયની તાકાત એ બહુપદીઓના તમામ નાના મૂળને સંયુક્ત રીતે શોધવાની ક્ષમતા છે. ઉસ્તાદનો પ્રસારણ હુમલો ઉસ્તાદના હુમલાનું સૌથી સરળ સ્વરૂપ સમજણને સરળ બનાવવા માટે રજૂ કરવામાં આવ્યું છે. સામાન્ય કેસ કોપરસ્મિથ પદ્ધતિનો ઉપયોગ કરે છે. ધારો કે એક પ્રેષક એક જ સંદેશ એન્ક્રિપ્ટેડ સ્વરૂપમાં સંખ્યાબંધ લોકોને મોકલે છે, દરેક એક જ નાના જાહેર એક્સ્પોનન્ટનો ઉપયોગ કરે છે, કહો, અને વિવિધ મોડ્યુલી. એક સરળ દલીલ દર્શાવે છે કે સિફરટેક્સ્ટ્સની જાણ થતાં જ, સંદેશ હવે સુરક્ષિત નથીઃ ધારો કે ઇવ ઇન્ટરસેપ્ટ કરે છે, અને, ક્યાં. આપણે બધા માટે ધારી શકીએ છીએ (અન્યથા, ગણતરી દ્વારા સંખ્યાઓમાંથી એકના પરિબળની ગણતરી કરવી શક્ય છે.) ચાઇનીઝ રિમેન્ડર થીયરમ દ્વારા, તે એવી ગણતરી કરી શકે છે. પછી; જો કે, બધા માટે, આપણી પાસે છે. આમ પૂર્ણાંકો પર આધાર રાખે છે, અને ઈવ મેળવવા માટે ઘનમૂળની ગણતરી કરી શકે છે. મોટા મૂલ્યો માટે, વધુ સાઇફરટેક્સ્ટ્સની જરૂર છે, ખાસ કરીને, સાઇફરટેક્સ્ટ્સ પૂરતા છે. સામાન્યીકરણ હાસ્ટાડે એ પણ દર્શાવ્યું હતું કે એન્ક્રિપ્શન પહેલાં રેખીય પેડિંગ લાગુ કરવાથી આ હુમલા સામે રક્ષણ મળતું નથી. ધારો કે હુમલાખોર શીખે છે કે કેટલાક રેખીય કાર્ય માટે, એટલે કે, બોબ સંદેશને એન્ક્રિપ્ટ કરતા પહેલા પેડ લાગુ કરે છે જેથી પ્રાપ્તકર્તાઓને થોડો અલગ સંદેશો પ્રાપ્ત થાય. દાખલા તરીકે, જો બિટ્સ લાંબા હોય, તો બોબ એન્ક્રિપ્ટ કરી શકે છે અને તેને-th પ્રાપ્તકર્તાને મોકલી શકે છે. જો લોકોનું મોટું પર્યાપ્ત જૂથ સામેલ હોય, તો હુમલાખોર સમાન પદ્ધતિઓ સાથે તમામ સાઇફરટેક્સ્ટમાંથી પ્લેનટેક્સ્ટને પુનઃપ્રાપ્ત કરી શકે છે. વધુ સામાન્યતામાં, હેસ્ટાદે સાબિત કર્યું કે જો પૂરતા પ્રમાણમાં ઘણા સમીકરણો પૂરા પાડવામાં આવે તો કોઈપણ નિશ્ચિત બહુપદી લાગુ કરવા જેવા પ્રમાણમાં મુખ્ય સંયોજનોમાં એકરૂપ સમીકરણોની પદ્ધતિ ઉકેલી શકાય છે. આ હુમલો સૂચવે છે કે આરએસએ એન્ક્રિપ્શનમાં રેન્ડમાઇઝ્ડ પેડિંગનો ઉપયોગ થવો જોઈએ. પ્રમેય 2 (હેસ્ટાડ) ધારો કે પ્રમાણમાં મુખ્ય પૂર્ણાંકો અને સમૂહ છે. ચાલો મહત્તમ ડિગ્રીની બહુપદીઓ હોઈએ. ધારો કે બધા માટે એક અનન્ય સંતોષ છે. વધુમાં, ધારો. એક કાર્યક્ષમ અલ્ગોરિધમ છે જે, બધા માટે આપવામાં આવે છે, ગણતરી કરે છે. પુરાવા પ્રમાણમાં મુખ્ય હોવાથી ચીની શેષ પ્રમેયનો ઉપયોગ સંતોષકારક અને બધા માટે ગુણાંકની ગણતરી કરવા માટે થઈ શકે છે. સેટિંગ, આપણે તે જાણીએ છીએ. તે બિન-શૂન્ય હોવાથી, આપણી પાસે તે પણ બિન-શૂન્ય છે. ની ડિગ્રી સૌથી વધુ છે. કોપરસ્મિથના પ્રમેય દ્વારા, આપણે સંતોષકારક અને તમામ પૂર્ણાંક મૂળની ગણતરી કરી શકીએ છીએ. જો કે, આપણે જાણીએ છીએ કે, કોપરસ્મિથના પ્રમેય દ્વારા મળેલા મૂળમાં પણ એવું જ છે. આ પ્રમેયને પ્રસારણ આર. એસ. એ. ની સમસ્યા પર નીચેની રીતે લાગુ કરી શકાય છેઃ ધારો કે-th પ્લેનટેક્સ્ટ બહુપદી સાથે ગાદીવાળું છે, જેથી. પછી સાચું છે, અને કોપરસ્મિથની પદ્ધતિનો ઉપયોગ કરી શકાય છે. હુમલો એકવાર સફળ થાય છે, સંદેશાઓની સંખ્યા ક્યાં છે. મૂળ પરિણામમાં સંપૂર્ણ કોપરસ્મિથ પદ્ધતિને બદલે હેસ્ટેડના પ્રકારનો ઉપયોગ કરવામાં આવ્યો હતો. પરિણામે, તેને સંદેશાઓની જરૂર હતી, ક્યાં. ફ્રેન્કલીન-રેઇટર સંબંધિત-સંદેશ હુમલો ફ્રેન્કલીન અને રેઇટરએ આરએસએ સામેના હુમલાને ઓળખી કાઢ્યો જ્યારે બહુવિધ સંબંધિત સંદેશાઓ એન્ક્રિપ્ટ થયેલ હોયઃ જો બે સંદેશાઓ માત્ર બે સંદેશાઓ વચ્ચેના જાણીતા નિશ્ચિત તફાવતથી અલગ હોય અને સમાન આરએસએ મોડ્યુલસ હેઠળ આરએસએ-એન્ક્રિપ્ટ થયેલ હોય, તો તે બંનેને પુનઃપ્રાપ્ત કરવાનું શક્ય છે. આ હુમલાનું મૂળ વર્ણન જાહેર પ્રતિનિધિ સાથે કરવામાં આવ્યું હતું, પરંતુ તે વધુ સામાન્ય રીતે કામ કરે છે (જેમ જેમ ખર્ચ વધે છે તેમ તેમ). ચાલો એલિસની સાર્વજનિક ચાવી બનીએ. ધારો કે કેટલાક સાર્વજનિક રીતે જાણીતા બહુપદી માટે બે અલગ અલગ સંદેશાઓ સંતોષકારક છે. એલિસને મોકલવા અને મોકલવા માટે, બોબ નિષ્કપટ રીતે સંદેશાઓને એન્ક્રિપ્ટ કરી શકે છે અને પરિણામી સિફરટેક્સ્ટ્સને પ્રસારિત કરી શકે છે. નીચે આપેલા પ્રમેયનો ઉપયોગ કરીને ઈવ સરળતાથી પુનઃપ્રાપ્ત કરી શકે છેઃ પ્રમેય 3 (ફ્રેન્કલીન-રેઇટર) ચાલો એક RSA જાહેર કી બનીએ. ચાલો સાથે કેટલીક રેખીય બહુપદી માટે સંતુષ્ટ કરીએ. પછી, આપેલ, હુમલાખોર (ઇવ) સમયના વર્ગમાં પુનઃપ્રાપ્ત કરી શકે છે. પુરાવો કારણ કે, આપણે જાણીએ છીએ કે તે બહુપદીનું મૂળ છે. તેવી જ રીતે, તેનું મૂળ છે. તેથી, રેખીય પરિબળ બંને બહુપદીઓને વિભાજિત કરે છે. તેથી, ઇવ અને ના સૌથી મોટા સામાન્ય ભાજકની ગણતરી કરી શકે છે, અને જો તે રેખીય હોવાનું બહાર આવે, તો તે મળી આવે છે. યુક્લિડિયન અલ્ગોરિધમનો ઉપયોગ કરીને અને તેનો ઉપયોગ કરીને ચતુર્ભુજ સમયમાં ગણતરી કરી શકાય છે. હેસ્ટાડ અને ફ્રેન્કલીન-રેઇટરના હુમલાઓની જેમ કોપરસ્મિથના શોર્ટ-પેડ હુમલા, આ હુમલો જાહેર પ્રતિનિધિ સાથે આરએસએની નબળાઈનો ફાયદો ઉઠાવે છે. કોપરસ્મિથે દર્શાવ્યું હતું કે જો હેસ્ટાડ દ્વારા સૂચવવામાં આવેલ રેન્ડમાઇઝ્ડ પેડિંગનો અયોગ્ય રીતે ઉપયોગ કરવામાં આવે, તો આરએસએ એન્ક્રિપ્શન સુરક્ષિત નથી. ધારો કે બોબ એલિસને એન્ક્રિપ્ટ કરતા પહેલા નાના રેન્ડમ પેડિંગનો ઉપયોગ કરીને સંદેશ મોકલે છે. એક હુમલાખોર, ઇવ, સાઇફરટેક્સ્ટને અટકાવે છે અને તેને તેના ગંતવ્ય સુધી પહોંચતા અટકાવે છે. બોબ એલિસને ફરીથી મોકલવાનું નક્કી કરે છે કારણ કે એલિસે તેના સંદેશનો જવાબ આપ્યો ન હતો. તે અવ્યવસ્થિત રીતે ફરીથી પેડ કરે છે અને પરિણામી સિફરટેક્સ્ટને પ્રસારિત કરે છે. ઇવ પાસે હવે બે અલગ અલગ રેન્ડમ પેડનો ઉપયોગ કરીને એક જ સંદેશના બે એન્ક્રિપ્શનને અનુરૂપ બે સિફરટેક્સ્ટ્સ છે. હવ્વાને રેન્ડમ પેડનો ઉપયોગ કરવામાં આવી રહ્યો છે તે ખબર ન હોવા છતાં, જો રેન્ડમ પેડિંગ ખૂબ નાનું હોય તો તે હજુ પણ નીચેના પ્રમેયનો ઉપયોગ કરીને સંદેશને પુનઃપ્રાપ્ત કરી શકે છે. પ્રમેય 4 (કોપરસ્મિથ) ચાલો એક સાર્વજનિક આર. એસ. એ. કી હોઈએ, જ્યાં બિટ્સ લાંબા હોય છે. સેટ કરો. ચાલો મોટાભાગના બિટ્સ પર લંબાઈનો સંદેશ બનો. વ્યાખ્યાયિત કરો અને, ક્યાં અને તેની સાથે અલગ પૂર્ણાંકો છે. જો ઇવ આપવામાં આવે અને એનક્રિપ્શન આપવામાં આવે (પરંતુ આપવામાં આવતું નથી અથવા), તો તે અસરકારક રીતે પુનઃપ્રાપ્ત કરી શકે છે. પુરાવો વ્યાખ્યાયિત કરો અને. આપણે જાણીએ છીએ કે ક્યારે, આ બહુપદીઓ સામાન્ય મૂળ તરીકે હોય છે. બીજા શબ્દોમાં કહીએ તો, તે પરિણામનું મૂળ છે. વધુમાં, તા. તેથી, તે મોડ્યુલોનું એક નાનું મૂળ છે, અને ઈવ કોપરસ્મિથ પદ્ધતિનો ઉપયોગ કરીને તેને અસરકારક રીતે શોધી શકે છે. એકવાર જાણ થઈ જાય પછી, ફ્રેન્કલીન-રેઇટર હુમલાનો ઉપયોગ પુનઃપ્રાપ્ત કરવા માટે અને પરિણામે થઈ શકે છે. આરઓસીએ હુમલા સંદર્ભો ક્રિપ્ટોગ્રાફિક હુમલાઓ જાહેર-કી ક્રિપ્ટોસિસ્ટમ્સ પરના હુમલાઓ પણ જુઓ.