diff -uNr a/eucrypt/mpi/COPYING b/eucrypt/mpi/COPYING --- a/eucrypt/mpi/COPYING false +++ b/eucrypt/mpi/COPYING 5b77e0898b3b6d0e202c38e9a85da30c6920c748463247e5ed6f1efc92c6794ce23ecbb83cdaed5cc79bffbf197c171b1de7fb872491b7a34966e1fb4d0e0d0f @@ -0,0 +1,676 @@ + + GNU GENERAL PUBLIC LICENSE + Version 3, 29 June 2007 + + Copyright (C) 2007 Free Software Foundation, Inc. + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + + Preamble + + The GNU General Public License is a free, copyleft license for +software and other kinds of works. + + The licenses for most software and other practical works are designed +to take away your freedom to share and change the works. By contrast, +the GNU General Public License is intended to guarantee your freedom to +share and change all versions of a program--to make sure it remains free +software for all its users. We, the Free Software Foundation, use the +GNU General Public License for most of our software; it applies also to +any other work released this way by its authors. You can apply it to +your programs, too. + + When we speak of free software, we are referring to freedom, not +price. Our General Public Licenses are designed to make sure that you +have the freedom to distribute copies of free software (and charge for +them if you wish), that you receive source code or can get it if you +want it, that you can change the software or use pieces of it in new +free programs, and that you know you can do these things. + + To protect your rights, we need to prevent others from denying you +these rights or asking you to surrender the rights. Therefore, you have +certain responsibilities if you distribute copies of the software, or if +you modify it: responsibilities to respect the freedom of others. + + For example, if you distribute copies of such a program, whether +gratis or for a fee, you must pass on to the recipients the same +freedoms that you received. You must make sure that they, too, receive +or can get the source code. And you must show them these terms so they +know their rights. + + Developers that use the GNU GPL protect your rights with two steps: +(1) assert copyright on the software, and (2) offer you this License +giving you legal permission to copy, distribute and/or modify it. + + For the developers' and authors' protection, the GPL clearly explains +that there is no warranty for this free software. For both users' and +authors' sake, the GPL requires that modified versions be marked as +changed, so that their problems will not be attributed erroneously to +authors of previous versions. + + Some devices are designed to deny users access to install or run +modified versions of the software inside them, although the manufacturer +can do so. This is fundamentally incompatible with the aim of +protecting users' freedom to change the software. The systematic +pattern of such abuse occurs in the area of products for individuals to +use, which is precisely where it is most unacceptable. Therefore, we +have designed this version of the GPL to prohibit the practice for those +products. If such problems arise substantially in other domains, we +stand ready to extend this provision to those domains in future versions +of the GPL, as needed to protect the freedom of users. + + Finally, every program is threatened constantly by software patents. +States should not allow patents to restrict development and use of +software on general-purpose computers, but in those that do, we wish to +avoid the special danger that patents applied to a free program could +make it effectively proprietary. To prevent this, the GPL assures that +patents cannot be used to render the program non-free. + + The precise terms and conditions for copying, distribution and +modification follow. + + TERMS AND CONDITIONS + + 0. Definitions. + + "This License" refers to version 3 of the GNU General Public License. + + "Copyright" also means copyright-like laws that apply to other kinds of +works, such as semiconductor masks. + + "The Program" refers to any copyrightable work licensed under this +License. Each licensee is addressed as "you". "Licensees" and +"recipients" may be individuals or organizations. + + To "modify" a work means to copy from or adapt all or part of the work +in a fashion requiring copyright permission, other than the making of an +exact copy. The resulting work is called a "modified version" of the +earlier work or a work "based on" the earlier work. + + A "covered work" means either the unmodified Program or a work based +on the Program. + + To "propagate" a work means to do anything with it that, without +permission, would make you directly or secondarily liable for +infringement under applicable copyright law, except executing it on a +computer or modifying a private copy. Propagation includes copying, +distribution (with or without modification), making available to the +public, and in some countries other activities as well. + + To "convey" a work means any kind of propagation that enables other +parties to make or receive copies. Mere interaction with a user through +a computer network, with no transfer of a copy, is not conveying. + + An interactive user interface displays "Appropriate Legal Notices" +to the extent that it includes a convenient and prominently visible +feature that (1) displays an appropriate copyright notice, and (2) +tells the user that there is no warranty for the work (except to the +extent that warranties are provided), that licensees may convey the +work under this License, and how to view a copy of this License. If +the interface presents a list of user commands or options, such as a +menu, a prominent item in the list meets this criterion. + + 1. Source Code. + + The "source code" for a work means the preferred form of the work +for making modifications to it. "Object code" means any non-source +form of a work. + + A "Standard Interface" means an interface that either is an official +standard defined by a recognized standards body, or, in the case of +interfaces specified for a particular programming language, one that +is widely used among developers working in that language. + + The "System Libraries" of an executable work include anything, other +than the work as a whole, that (a) is included in the normal form of +packaging a Major Component, but which is not part of that Major +Component, and (b) serves only to enable use of the work with that +Major Component, or to implement a Standard Interface for which an +implementation is available to the public in source code form. A +"Major Component", in this context, means a major essential component +(kernel, window system, and so on) of the specific operating system +(if any) on which the executable work runs, or a compiler used to +produce the work, or an object code interpreter used to run it. + + The "Corresponding Source" for a work in object code form means all +the source code needed to generate, install, and (for an executable +work) run the object code and to modify the work, including scripts to +control those activities. However, it does not include the work's +System Libraries, or general-purpose tools or generally available free +programs which are used unmodified in performing those activities but +which are not part of the work. For example, Corresponding Source +includes interface definition files associated with source files for +the work, and the source code for shared libraries and dynamically +linked subprograms that the work is specifically designed to require, +such as by intimate data communication or control flow between those +subprograms and other parts of the work. + + The Corresponding Source need not include anything that users +can regenerate automatically from other parts of the Corresponding +Source. + + The Corresponding Source for a work in source code form is that +same work. + + 2. Basic Permissions. + + All rights granted under this License are granted for the term of +copyright on the Program, and are irrevocable provided the stated +conditions are met. This License explicitly affirms your unlimited +permission to run the unmodified Program. The output from running a +covered work is covered by this License only if the output, given its +content, constitutes a covered work. This License acknowledges your +rights of fair use or other equivalent, as provided by copyright law. + + You may make, run and propagate covered works that you do not +convey, without conditions so long as your license otherwise remains +in force. You may convey covered works to others for the sole purpose +of having them make modifications exclusively for you, or provide you +with facilities for running those works, provided that you comply with +the terms of this License in conveying all material for which you do +not control copyright. Those thus making or running the covered works +for you must do so exclusively on your behalf, under your direction +and control, on terms that prohibit them from making any copies of +your copyrighted material outside their relationship with you. + + Conveying under any other circumstances is permitted solely under +the conditions stated below. Sublicensing is not allowed; section 10 +makes it unnecessary. + + 3. Protecting Users' Legal Rights From Anti-Circumvention Law. + + No covered work shall be deemed part of an effective technological +measure under any applicable law fulfilling obligations under article +11 of the WIPO copyright treaty adopted on 20 December 1996, or +similar laws prohibiting or restricting circumvention of such +measures. + + When you convey a covered work, you waive any legal power to forbid +circumvention of technological measures to the extent such circumvention +is effected by exercising rights under this License with respect to +the covered work, and you disclaim any intention to limit operation or +modification of the work as a means of enforcing, against the work's +users, your or third parties' legal rights to forbid circumvention of +technological measures. + + 4. Conveying Verbatim Copies. + + You may convey verbatim copies of the Program's source code as you +receive it, in any medium, provided that you conspicuously and +appropriately publish on each copy an appropriate copyright notice; +keep intact all notices stating that this License and any +non-permissive terms added in accord with section 7 apply to the code; +keep intact all notices of the absence of any warranty; and give all +recipients a copy of this License along with the Program. + + You may charge any price or no price for each copy that you convey, +and you may offer support or warranty protection for a fee. + + 5. Conveying Modified Source Versions. + + You may convey a work based on the Program, or the modifications to +produce it from the Program, in the form of source code under the +terms of section 4, provided that you also meet all of these conditions: + + a) The work must carry prominent notices stating that you modified + it, and giving a relevant date. + + b) The work must carry prominent notices stating that it is + released under this License and any conditions added under section + 7. This requirement modifies the requirement in section 4 to + "keep intact all notices". + + c) You must license the entire work, as a whole, under this + License to anyone who comes into possession of a copy. This + License will therefore apply, along with any applicable section 7 + additional terms, to the whole of the work, and all its parts, + regardless of how they are packaged. This License gives no + permission to license the work in any other way, but it does not + invalidate such permission if you have separately received it. + + d) If the work has interactive user interfaces, each must display + Appropriate Legal Notices; however, if the Program has interactive + interfaces that do not display Appropriate Legal Notices, your + work need not make them do so. + + A compilation of a covered work with other separate and independent +works, which are not by their nature extensions of the covered work, +and which are not combined with it such as to form a larger program, +in or on a volume of a storage or distribution medium, is called an +"aggregate" if the compilation and its resulting copyright are not +used to limit the access or legal rights of the compilation's users +beyond what the individual works permit. Inclusion of a covered work +in an aggregate does not cause this License to apply to the other +parts of the aggregate. + + 6. Conveying Non-Source Forms. + + You may convey a covered work in object code form under the terms +of sections 4 and 5, provided that you also convey the +machine-readable Corresponding Source under the terms of this License, +in one of these ways: + + a) Convey the object code in, or embodied in, a physical product + (including a physical distribution medium), accompanied by the + Corresponding Source fixed on a durable physical medium + customarily used for software interchange. + + b) Convey the object code in, or embodied in, a physical product + (including a physical distribution medium), accompanied by a + written offer, valid for at least three years and valid for as + long as you offer spare parts or customer support for that product + model, to give anyone who possesses the object code either (1) a + copy of the Corresponding Source for all the software in the + product that is covered by this License, on a durable physical + medium customarily used for software interchange, for a price no + more than your reasonable cost of physically performing this + conveying of source, or (2) access to copy the + Corresponding Source from a network server at no charge. + + c) Convey individual copies of the object code with a copy of the + written offer to provide the Corresponding Source. This + alternative is allowed only occasionally and noncommercially, and + only if you received the object code with such an offer, in accord + with subsection 6b. + + d) Convey the object code by offering access from a designated + place (gratis or for a charge), and offer equivalent access to the + Corresponding Source in the same way through the same place at no + further charge. You need not require recipients to copy the + Corresponding Source along with the object code. If the place to + copy the object code is a network server, the Corresponding Source + may be on a different server (operated by you or a third party) + that supports equivalent copying facilities, provided you maintain + clear directions next to the object code saying where to find the + Corresponding Source. Regardless of what server hosts the + Corresponding Source, you remain obligated to ensure that it is + available for as long as needed to satisfy these requirements. + + e) Convey the object code using peer-to-peer transmission, provided + you inform other peers where the object code and Corresponding + Source of the work are being offered to the general public at no + charge under subsection 6d. + + A separable portion of the object code, whose source code is excluded +from the Corresponding Source as a System Library, need not be +included in conveying the object code work. + + A "User Product" is either (1) a "consumer product", which means any +tangible personal property which is normally used for personal, family, +or household purposes, or (2) anything designed or sold for incorporation +into a dwelling. In determining whether a product is a consumer product, +doubtful cases shall be resolved in favor of coverage. For a particular +product received by a particular user, "normally used" refers to a +typical or common use of that class of product, regardless of the status +of the particular user or of the way in which the particular user +actually uses, or expects or is expected to use, the product. A product +is a consumer product regardless of whether the product has substantial +commercial, industrial or non-consumer uses, unless such uses represent +the only significant mode of use of the product. + + "Installation Information" for a User Product means any methods, +procedures, authorization keys, or other information required to install +and execute modified versions of a covered work in that User Product from +a modified version of its Corresponding Source. The information must +suffice to ensure that the continued functioning of the modified object +code is in no case prevented or interfered with solely because +modification has been made. + + If you convey an object code work under this section in, or with, or +specifically for use in, a User Product, and the conveying occurs as +part of a transaction in which the right of possession and use of the +User Product is transferred to the recipient in perpetuity or for a +fixed term (regardless of how the transaction is characterized), the +Corresponding Source conveyed under this section must be accompanied +by the Installation Information. But this requirement does not apply +if neither you nor any third party retains the ability to install +modified object code on the User Product (for example, the work has +been installed in ROM). + + The requirement to provide Installation Information does not include a +requirement to continue to provide support service, warranty, or updates +for a work that has been modified or installed by the recipient, or for +the User Product in which it has been modified or installed. Access to a +network may be denied when the modification itself materially and +adversely affects the operation of the network or violates the rules and +protocols for communication across the network. + + Corresponding Source conveyed, and Installation Information provided, +in accord with this section must be in a format that is publicly +documented (and with an implementation available to the public in +source code form), and must require no special password or key for +unpacking, reading or copying. + + 7. Additional Terms. + + "Additional permissions" are terms that supplement the terms of this +License by making exceptions from one or more of its conditions. +Additional permissions that are applicable to the entire Program shall +be treated as though they were included in this License, to the extent +that they are valid under applicable law. If additional permissions +apply only to part of the Program, that part may be used separately +under those permissions, but the entire Program remains governed by +this License without regard to the additional permissions. + + When you convey a copy of a covered work, you may at your option +remove any additional permissions from that copy, or from any part of +it. (Additional permissions may be written to require their own +removal in certain cases when you modify the work.) You may place +additional permissions on material, added by you to a covered work, +for which you have or can give appropriate copyright permission. + + Notwithstanding any other provision of this License, for material you +add to a covered work, you may (if authorized by the copyright holders of +that material) supplement the terms of this License with terms: + + a) Disclaiming warranty or limiting liability differently from the + terms of sections 15 and 16 of this License; or + + b) Requiring preservation of specified reasonable legal notices or + author attributions in that material or in the Appropriate Legal + Notices displayed by works containing it; or + + c) Prohibiting misrepresentation of the origin of that material, or + requiring that modified versions of such material be marked in + reasonable ways as different from the original version; or + + d) Limiting the use for publicity purposes of names of licensors or + authors of the material; or + + e) Declining to grant rights under trademark law for use of some + trade names, trademarks, or service marks; or + + f) Requiring indemnification of licensors and authors of that + material by anyone who conveys the material (or modified versions of + it) with contractual assumptions of liability to the recipient, for + any liability that these contractual assumptions directly impose on + those licensors and authors. + + All other non-permissive additional terms are considered "further +restrictions" within the meaning of section 10. If the Program as you +received it, or any part of it, contains a notice stating that it is +governed by this License along with a term that is a further +restriction, you may remove that term. If a license document contains +a further restriction but permits relicensing or conveying under this +License, you may add to a covered work material governed by the terms +of that license document, provided that the further restriction does +not survive such relicensing or conveying. + + If you add terms to a covered work in accord with this section, you +must place, in the relevant source files, a statement of the +additional terms that apply to those files, or a notice indicating +where to find the applicable terms. + + Additional terms, permissive or non-permissive, may be stated in the +form of a separately written license, or stated as exceptions; +the above requirements apply either way. + + 8. Termination. + + You may not propagate or modify a covered work except as expressly +provided under this License. Any attempt otherwise to propagate or +modify it is void, and will automatically terminate your rights under +this License (including any patent licenses granted under the third +paragraph of section 11). + + However, if you cease all violation of this License, then your +license from a particular copyright holder is reinstated (a) +provisionally, unless and until the copyright holder explicitly and +finally terminates your license, and (b) permanently, if the copyright +holder fails to notify you of the violation by some reasonable means +prior to 60 days after the cessation. + + Moreover, your license from a particular copyright holder is +reinstated permanently if the copyright holder notifies you of the +violation by some reasonable means, this is the first time you have +received notice of violation of this License (for any work) from that +copyright holder, and you cure the violation prior to 30 days after +your receipt of the notice. + + Termination of your rights under this section does not terminate the +licenses of parties who have received copies or rights from you under +this License. If your rights have been terminated and not permanently +reinstated, you do not qualify to receive new licenses for the same +material under section 10. + + 9. Acceptance Not Required for Having Copies. + + You are not required to accept this License in order to receive or +run a copy of the Program. Ancillary propagation of a covered work +occurring solely as a consequence of using peer-to-peer transmission +to receive a copy likewise does not require acceptance. However, +nothing other than this License grants you permission to propagate or +modify any covered work. These actions infringe copyright if you do +not accept this License. Therefore, by modifying or propagating a +covered work, you indicate your acceptance of this License to do so. + + 10. Automatic Licensing of Downstream Recipients. + + Each time you convey a covered work, the recipient automatically +receives a license from the original licensors, to run, modify and +propagate that work, subject to this License. You are not responsible +for enforcing compliance by third parties with this License. + + An "entity transaction" is a transaction transferring control of an +organization, or substantially all assets of one, or subdividing an +organization, or merging organizations. If propagation of a covered +work results from an entity transaction, each party to that +transaction who receives a copy of the work also receives whatever +licenses to the work the party's predecessor in interest had or could +give under the previous paragraph, plus a right to possession of the +Corresponding Source of the work from the predecessor in interest, if +the predecessor has it or can get it with reasonable efforts. + + You may not impose any further restrictions on the exercise of the +rights granted or affirmed under this License. For example, you may +not impose a license fee, royalty, or other charge for exercise of +rights granted under this License, and you may not initiate litigation +(including a cross-claim or counterclaim in a lawsuit) alleging that +any patent claim is infringed by making, using, selling, offering for +sale, or importing the Program or any portion of it. + + 11. Patents. + + A "contributor" is a copyright holder who authorizes use under this +License of the Program or a work on which the Program is based. The +work thus licensed is called the contributor's "contributor version". + + A contributor's "essential patent claims" are all patent claims +owned or controlled by the contributor, whether already acquired or +hereafter acquired, that would be infringed by some manner, permitted +by this License, of making, using, or selling its contributor version, +but do not include claims that would be infringed only as a +consequence of further modification of the contributor version. For +purposes of this definition, "control" includes the right to grant +patent sublicenses in a manner consistent with the requirements of +this License. + + Each contributor grants you a non-exclusive, worldwide, royalty-free +patent license under the contributor's essential patent claims, to +make, use, sell, offer for sale, import and otherwise run, modify and +propagate the contents of its contributor version. + + In the following three paragraphs, a "patent license" is any express +agreement or commitment, however denominated, not to enforce a patent +(such as an express permission to practice a patent or covenant not to +sue for patent infringement). To "grant" such a patent license to a +party means to make such an agreement or commitment not to enforce a +patent against the party. + + If you convey a covered work, knowingly relying on a patent license, +and the Corresponding Source of the work is not available for anyone +to copy, free of charge and under the terms of this License, through a +publicly available network server or other readily accessible means, +then you must either (1) cause the Corresponding Source to be so +available, or (2) arrange to deprive yourself of the benefit of the +patent license for this particular work, or (3) arrange, in a manner +consistent with the requirements of this License, to extend the patent +license to downstream recipients. "Knowingly relying" means you have +actual knowledge that, but for the patent license, your conveying the +covered work in a country, or your recipient's use of the covered work +in a country, would infringe one or more identifiable patents in that +country that you have reason to believe are valid. + + If, pursuant to or in connection with a single transaction or +arrangement, you convey, or propagate by procuring conveyance of, a +covered work, and grant a patent license to some of the parties +receiving the covered work authorizing them to use, propagate, modify +or convey a specific copy of the covered work, then the patent license +you grant is automatically extended to all recipients of the covered +work and works based on it. + + A patent license is "discriminatory" if it does not include within +the scope of its coverage, prohibits the exercise of, or is +conditioned on the non-exercise of one or more of the rights that are +specifically granted under this License. You may not convey a covered +work if you are a party to an arrangement with a third party that is +in the business of distributing software, under which you make payment +to the third party based on the extent of your activity of conveying +the work, and under which the third party grants, to any of the +parties who would receive the covered work from you, a discriminatory +patent license (a) in connection with copies of the covered work +conveyed by you (or copies made from those copies), or (b) primarily +for and in connection with specific products or compilations that +contain the covered work, unless you entered into that arrangement, +or that patent license was granted, prior to 28 March 2007. + + Nothing in this License shall be construed as excluding or limiting +any implied license or other defenses to infringement that may +otherwise be available to you under applicable patent law. + + 12. No Surrender of Others' Freedom. + + If conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot convey a +covered work so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you may +not convey it at all. For example, if you agree to terms that obligate you +to collect a royalty for further conveying from those to whom you convey +the Program, the only way you could satisfy both those terms and this +License would be to refrain entirely from conveying the Program. + + 13. Use with the GNU Affero General Public License. + + Notwithstanding any other provision of this License, you have +permission to link or combine any covered work with a work licensed +under version 3 of the GNU Affero General Public License into a single +combined work, and to convey the resulting work. The terms of this +License will continue to apply to the part which is the covered work, +but the special requirements of the GNU Affero General Public License, +section 13, concerning interaction through a network will apply to the +combination as such. + + 14. Revised Versions of this License. + + The Free Software Foundation may publish revised and/or new versions of +the GNU General Public License from time to time. Such new versions will +be similar in spirit to the present version, but may differ in detail to +address new problems or concerns. + + Each version is given a distinguishing version number. If the +Program specifies that a certain numbered version of the GNU General +Public License "or any later version" applies to it, you have the +option of following the terms and conditions either of that numbered +version or of any later version published by the Free Software +Foundation. If the Program does not specify a version number of the +GNU General Public License, you may choose any version ever published +by the Free Software Foundation. + + If the Program specifies that a proxy can decide which future +versions of the GNU General Public License can be used, that proxy's +public statement of acceptance of a version permanently authorizes you +to choose that version for the Program. + + Later license versions may give you additional or different +permissions. However, no additional obligations are imposed on any +author or copyright holder as a result of your choosing to follow a +later version. + + 15. Disclaimer of Warranty. + + THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY +APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT +HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY +OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, +THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM +IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF +ALL NECESSARY SERVICING, REPAIR OR CORRECTION. + + 16. Limitation of Liability. + + IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING +WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MODIFIES AND/OR CONVEYS +THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY +GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE +USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF +DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD +PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), +EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF +SUCH DAMAGES. + + 17. Interpretation of Sections 15 and 16. + + If the disclaimer of warranty and limitation of liability provided +above cannot be given local legal effect according to their terms, +reviewing courts shall apply local law that most closely approximates +an absolute waiver of all civil liability in connection with the +Program, unless a warranty or assumption of liability accompanies a +copy of the Program in return for a fee. + + END OF TERMS AND CONDITIONS + + How to Apply These Terms to Your New Programs + + If you develop a new program, and you want it to be of the greatest +possible use to the public, the best way to achieve this is to make it +free software which everyone can redistribute and change under these terms. + + To do so, attach the following notices to the program. It is safest +to attach them to the start of each source file to most effectively +state the exclusion of warranty; and each file should have at least +the "copyright" line and a pointer to where the full notice is found. + + + Copyright (C) + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . + +Also add information on how to contact you by electronic and paper mail. + + If the program does terminal interaction, make it output a short +notice like this when it starts in an interactive mode: + + Copyright (C) + This program comes with ABSOLUTELY NO WARRANTY; for details type `show w'. + This is free software, and you are welcome to redistribute it + under certain conditions; type `show c' for details. + +The hypothetical commands `show w' and `show c' should show the appropriate +parts of the General Public License. Of course, your program's commands +might be different; for a GUI interface, you would use an "about box". + + You should also get your employer (if you work as a programmer) or school, +if any, to sign a "copyright disclaimer" for the program, if necessary. +For more information on this, and how to apply and follow the GNU GPL, see +. + + The GNU General Public License does not permit incorporating your program +into proprietary programs. If your program is a subroutine library, you +may consider it more useful to permit linking proprietary applications with +the library. If this is what you want to do, use the GNU Lesser General +Public License instead of this License. But first, please read +. + diff -uNr a/eucrypt/mpi/Makefile b/eucrypt/mpi/Makefile --- a/eucrypt/mpi/Makefile false +++ b/eucrypt/mpi/Makefile 602e3b72a508c925a7c892db33a87a5183755d4e1413c8237dc368f49cf21e92728f65ec419b50245693588fd73f72e8f74632ada327390533b6c02523172402 @@ -0,0 +1,26 @@ +PROGRAM = mpi.a + +BUILD=obj +DIST=bin + +CXX = gcc +OBJECTS = $(addprefix $(BUILD)/, $(patsubst %.c,%.o,$(wildcard *.c))) +FLAGS = -g -Wall +INCLUDE = -I include + +.SUFFIXES: .o .c + +$(BUILD)/%.o: + $(CXX) $(FLAGS) $(INCLUDE) -c $*.c -o $@ + +all: $(PROGRAM) + +$(PROGRAM): $(OBJECTS) + ar rcs $(DIST)/$(PROGRAM) $(OBJECTS) + #ld -o $(DIST)/$(PROGRAM).o $(OBJECTS) -lc + +clean : + rm -rf nul core *flymake* $(BUILD)/*.o $(DIST)/$(PROGRAM) *~ bin/* + +check-syntax: + $(CXX) -c $(FLAGS) $(INCLUDE) -o nul -Wall -S $(CHK_SOURCES) diff -uNr a/eucrypt/mpi/README b/eucrypt/mpi/README --- a/eucrypt/mpi/README fe2917ef90a8e9deb4d9f7450cbbc20fdf3ca9f76630b6956137b4648916e143c89f857e0bf0fde968fd241f3049050ef7f146254a9e8daead54fc0b720c7620 +++ b/eucrypt/mpi/README 553fd1dbee5e1f5d3a5ec56690fea143943cd029cb4db51651f1ba01ee3069385ea513f0ce5c22a062020a3acef6cac219d0d86ccc56cb2467605776949f915b @@ -1,2 +1,86 @@ -S.MG, 2017 +What you see here is a very classic version of the GNU MPI (bignum) library. +It has been surgically removed from GnuPG 1.4.10, specifically as found at: +http://trilema.com/wp-content/uploads/2015/10/gnupg-1.4.10.tar.gz.asc + +SHA512(gnupg-1.4.10.tar.gz) : +d037041d2e6882fd3b999500b5a7b42be2c224836afc358e1f8a2465c1b74473d518f185b7c324b2c8dec4ffb70e9e34a03c94d1a54cc55d297f40c9745f6e1b + +DEMO: + +1) make +2) cd tests +3) make +4) ./test_mpi +5) output is: + 37A063D056817668C7AA3418F29 +6) q: 'Waaaaaa, it barfed!' + a: You are probably using GCC 5 or LLVM. Stop. + + +CHANGES FROM ORIGINAL: + +1) Everything pertaining to Automake was nuked, and the earth where it stood - + salted. + + Instead, we now have a conventional Makefile. It builds precisely + ONE THING - a single 'mpi.a' library suitable for static linking into + another project. This will turn up in 'bin'. + + Among other things, this now means that all KNOBS now reside in a + MANUALLY-controlled 'knobs.h' found in 'include'. If you are building + on some very peculiar unix, please read it and adjust as appropriate. + It contains ONLY those knobs which actually pertain to the code. + + The Makefile contains a 'check-syntax' - users of Emacs and Flymake + will see proper error-highlighting. + +2) ALL chip-specific ASM optimizations (including those found in longlong.h) + have been nuked. + +3) GPG-specific cruft has been amputated to the extent practical. + + The logging system has been retained, but it can be easily torn out, + which I may choose to do in the near future. + + The I/O buffering system has been retained. I may choose to remove it + in the near future. + + The 'secure memory' (unpageable alloc) system has been retained. + + 'Localization' and all related idiocies have been nuked. + Write hieroglyphs at home, leave them there, civilized folk + don't need'em in their source code. + +4) Other code has been altered solely to the extent required by items + (1), (2), and (3). + + Cruft which appears in dead #ifdefs may be removed in the future. + Don't get comfortable with it being there. + +5) Readers who wish to know EXACTLY what I changed, should get a copy of the + original tarball and write a simple script involving 'find' and 'vdiff', + which sadly did not fit in the margins of this page. + +6) To use the library, include 'include/mpi.h' in your project, + and statically link with 'bin/mpi.a'. + +7) The original code was distributed under GPL 3, which may apply on + your planet and is therefore included. (See COPYING.) + +---------- +UPDATE #1: +---------- + +1) Abolished the logging subsystem inherited from GPG. + +2) Abolished the I/O buffering subsystem, from same. + +3) Eliminated all #ifdef blocks pertaining to RiscOS. + +4) config.h is now knobs.h and is considerably shorter + on account of there now being a great many fewer knobs. + +5) Eliminated certain blocks of dead code. + +6) Inserted notice of modifications as specified in GPL-3 diff -uNr a/eucrypt/mpi/bin/README b/eucrypt/mpi/bin/README --- a/eucrypt/mpi/bin/README false +++ b/eucrypt/mpi/bin/README 15f92b08b27c8218ff3311087efb3cfde38a237f153b1708f4011fa1e14c0a21543720156b24e037bde2e43b02e8f3962a17689b6ca9e7ada38f84b40584eb59 @@ -0,0 +1 @@ +bin folder for mpi lib diff -uNr a/eucrypt/mpi/include/knobs.h b/eucrypt/mpi/include/knobs.h --- a/eucrypt/mpi/include/knobs.h false +++ b/eucrypt/mpi/include/knobs.h 1e58d3eca9c3cc986a0b371f931498784570bbaecb5dcf98e85f159c2e7fff90ccb30063da8ca10f6d9d6c9e25deeace497436496e3d48ef4ae49f364d02182c @@ -0,0 +1,75 @@ +/* knobs.h -- Originally generated from config.h.in by autoconf. + * But there is no more autoconf in this project. + * + * No Such Labs. (C) 2015. See README. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . +*/ + +#ifndef GNUPG_CONFIG_H_INCLUDED +#define GNUPG_CONFIG_H_INCLUDED + +/* Report memory usage. */ +//#define M_DEBUG 1 + +/* Define to 1 if you have the `atexit' function. */ +#define HAVE_ATEXIT 1 + +/* Defined if the mlock() call does not work */ +/* #undef HAVE_BROKEN_MLOCK */ + +/* Defined if a `byte' is typedef'd */ +/* #undef HAVE_BYTE_TYPEDEF */ + +/* defined if we run on some of the PCDOS like systems (DOS, Windoze. OS/2) + with special properties like no file modes */ +/* #undef HAVE_DOSISH_SYSTEM */ + +/* Define to 1 if you have the `getpagesize' function. */ +#define HAVE_GETPAGESIZE 1 + +/* Define to 1 if you have the header file. */ +#define HAVE_INTTYPES_H 1 + +/* Define to 1 if you have the `memmove' function. */ +#define HAVE_MEMMOVE 1 + +/* Defined if the system supports an mlock() call */ +#define HAVE_MLOCK 1 + +/* Define to 1 if you have the `mmap' function. */ +#define HAVE_MMAP 1 + +/* Define to 1 if you have the `plock' function. */ +/* #undef HAVE_PLOCK */ + +/* Define to 1 if you have the `raise' function. */ +#define HAVE_RAISE 1 + +/* Define to 1 if you have the `sysconf' function. */ +#define HAVE_SYSCONF 1 + +/* Defined if a `u16' is typedef'd */ +/* #undef HAVE_U16_TYPEDEF */ + +/* Defined if a `u32' is typedef'd */ +/* #undef HAVE_U32_TYPEDEF */ + +/* Defined if a `ulong' is typedef'd */ +#define HAVE_ULONG_TYPEDEF 1 + +/* Defined if a `ushort' is typedef'd */ +#define HAVE_USHORT_TYPEDEF 1 + +#endif /*GNUPG_CONFIG_H_INCLUDED*/ diff -uNr a/eucrypt/mpi/include/longlong.h b/eucrypt/mpi/include/longlong.h --- a/eucrypt/mpi/include/longlong.h false +++ b/eucrypt/mpi/include/longlong.h 0418e5bde9c91ccf99bc408f3088aa1ef37c3f8318ebc3babc9d9ab283a2ed3b158f0057ed885b0c336c69c4f58ac1ff4721d9188072dec45391c0f2cca7b250 @@ -0,0 +1,226 @@ +/* longlong.h -- definitions for mixed size 32/64 bit arithmetic. + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . +*/ + +/* You have to define the following before including this file: + + UWtype -- An unsigned type, default type for operations (typically a "word") + UHWtype -- An unsigned type, at least half the size of UWtype. + UDWtype -- An unsigned type, at least twice as large a UWtype + W_TYPE_SIZE -- size in bits of UWtype + + SItype, USItype -- Signed and unsigned 32 bit types. + DItype, UDItype -- Signed and unsigned 64 bit types. + + On a 32 bit machine UWtype should typically be USItype; + on a 64 bit machine, UWtype should typically be UDItype. +*/ + +#define __BITS4 (W_TYPE_SIZE / 4) +#define __ll_B ((UWtype) 1 << (W_TYPE_SIZE / 2)) +#define __ll_lowpart(t) ((UWtype) (t) & (__ll_B - 1)) +#define __ll_highpart(t) ((UWtype) (t) >> (W_TYPE_SIZE / 2)) + +/* This is used to make sure no undesirable sharing between different libraries + that use this file takes place. */ +#ifndef __MPN +#define __MPN(x) __##x +#endif + +/*************************************** + *********** Generic Versions ******** + ***************************************/ +#if !defined (umul_ppmm) && defined (__umulsidi3) +#define umul_ppmm(ph, pl, m0, m1) \ + { \ + UDWtype __ll = __umulsidi3 (m0, m1); \ + ph = (UWtype) (__ll >> W_TYPE_SIZE); \ + pl = (UWtype) __ll; \ + } +#endif + +#if !defined (__umulsidi3) +#define __umulsidi3(u, v) \ + ({UWtype __hi, __lo; \ + umul_ppmm (__hi, __lo, u, v); \ + ((UDWtype) __hi << W_TYPE_SIZE) | __lo; }) +#endif + +/* If this machine has no inline assembler, use C macros. */ + +#if !defined (add_ssaaaa) +#define add_ssaaaa(sh, sl, ah, al, bh, bl) \ + do { \ + UWtype __x; \ + __x = (al) + (bl); \ + (sh) = (ah) + (bh) + (__x < (al)); \ + (sl) = __x; \ + } while (0) +#endif + +#if !defined (sub_ddmmss) +#define sub_ddmmss(sh, sl, ah, al, bh, bl) \ + do { \ + UWtype __x; \ + __x = (al) - (bl); \ + (sh) = (ah) - (bh) - (__x > (al)); \ + (sl) = __x; \ + } while (0) +#endif + +#if !defined (umul_ppmm) +#define umul_ppmm(w1, w0, u, v) \ + do { \ + UWtype __x0, __x1, __x2, __x3; \ + UHWtype __ul, __vl, __uh, __vh; \ + UWtype __u = (u), __v = (v); \ + \ + __ul = __ll_lowpart (__u); \ + __uh = __ll_highpart (__u); \ + __vl = __ll_lowpart (__v); \ + __vh = __ll_highpart (__v); \ + \ + __x0 = (UWtype) __ul * __vl; \ + __x1 = (UWtype) __ul * __vh; \ + __x2 = (UWtype) __uh * __vl; \ + __x3 = (UWtype) __uh * __vh; \ + \ + __x1 += __ll_highpart (__x0);/* this can't give carry */ \ + __x1 += __x2; /* but this indeed can */ \ + if (__x1 < __x2) /* did we get it? */ \ + __x3 += __ll_B; /* yes, add it in the proper pos. */ \ + \ + (w1) = __x3 + __ll_highpart (__x1); \ + (w0) = (__ll_lowpart (__x1) << W_TYPE_SIZE/2) + __ll_lowpart (__x0);\ + } while (0) +#endif + +#if !defined (umul_ppmm) +#define smul_ppmm(w1, w0, u, v) \ + do { \ + UWtype __w1; \ + UWtype __m0 = (u), __m1 = (v); \ + umul_ppmm (__w1, w0, __m0, __m1); \ + (w1) = __w1 - (-(__m0 >> (W_TYPE_SIZE - 1)) & __m1) \ + - (-(__m1 >> (W_TYPE_SIZE - 1)) & __m0); \ + } while (0) +#endif + +/* Define this unconditionally, so it can be used for debugging. */ +#define __udiv_qrnnd_c(q, r, n1, n0, d) \ + do { \ + UWtype __d1, __d0, __q1, __q0, __r1, __r0, __m; \ + __d1 = __ll_highpart (d); \ + __d0 = __ll_lowpart (d); \ + \ + __r1 = (n1) % __d1; \ + __q1 = (n1) / __d1; \ + __m = (UWtype) __q1 * __d0; \ + __r1 = __r1 * __ll_B | __ll_highpart (n0); \ + if (__r1 < __m) \ + { \ + __q1--, __r1 += (d); \ + if (__r1 >= (d)) /* i.e. we didn't get carry when adding to __r1 */\ + if (__r1 < __m) \ + __q1--, __r1 += (d); \ + } \ + __r1 -= __m; \ + \ + __r0 = __r1 % __d1; \ + __q0 = __r1 / __d1; \ + __m = (UWtype) __q0 * __d0; \ + __r0 = __r0 * __ll_B | __ll_lowpart (n0); \ + if (__r0 < __m) \ + { \ + __q0--, __r0 += (d); \ + if (__r0 >= (d)) \ + if (__r0 < __m) \ + __q0--, __r0 += (d); \ + } \ + __r0 -= __m; \ + \ + (q) = (UWtype) __q1 * __ll_B | __q0; \ + (r) = __r0; \ + } while (0) + +/* If the processor has no udiv_qrnnd but sdiv_qrnnd, go through + __udiv_w_sdiv (defined in libgcc or elsewhere). */ +#if !defined (udiv_qrnnd) && defined (sdiv_qrnnd) +#define udiv_qrnnd(q, r, nh, nl, d) \ + do { \ + UWtype __r; \ + (q) = __MPN(udiv_w_sdiv) (&__r, nh, nl, d); \ + (r) = __r; \ + } while (0) +#endif + +/* If udiv_qrnnd was not defined for this processor, use __udiv_qrnnd_c. */ +#if !defined (udiv_qrnnd) +#define UDIV_NEEDS_NORMALIZATION 1 +#define udiv_qrnnd __udiv_qrnnd_c +#endif + +#if !defined (count_leading_zeros) +extern +#ifdef __STDC__ +const +#endif +unsigned char __clz_tab[]; +#define MPI_INTERNAL_NEED_CLZ_TAB 1 +#define count_leading_zeros(count, x) \ + do { \ + UWtype __xr = (x); \ + UWtype __a; \ + \ + if (W_TYPE_SIZE <= 32) \ + { \ + __a = __xr < ((UWtype) 1 << 2*__BITS4) \ + ? (__xr < ((UWtype) 1 << __BITS4) ? 0 : __BITS4) \ + : (__xr < ((UWtype) 1 << 3*__BITS4) ? 2*__BITS4 : 3*__BITS4);\ + } \ + else \ + { \ + for (__a = W_TYPE_SIZE - 8; __a > 0; __a -= 8) \ + if (((__xr >> __a) & 0xff) != 0) \ + break; \ + } \ + \ + (count) = W_TYPE_SIZE - (__clz_tab[__xr >> __a] + __a); \ + } while (0) +/* This version gives a well-defined value for zero. */ +#define COUNT_LEADING_ZEROS_0 W_TYPE_SIZE +#endif + +#if !defined (count_trailing_zeros) +/* Define count_trailing_zeros using count_leading_zeros. The latter might be + defined in asm, but if it is not, the C version above is good enough. */ +#define count_trailing_zeros(count, x) \ + do { \ + UWtype __ctz_x = (x); \ + UWtype __ctz_c; \ + count_leading_zeros (__ctz_c, __ctz_x & -__ctz_x); \ + (count) = W_TYPE_SIZE - 1 - __ctz_c; \ + } while (0) +#endif + +#ifndef UDIV_NEEDS_NORMALIZATION +#define UDIV_NEEDS_NORMALIZATION 0 +#endif diff -uNr a/eucrypt/mpi/include/memory.h b/eucrypt/mpi/include/memory.h --- a/eucrypt/mpi/include/memory.h false +++ b/eucrypt/mpi/include/memory.h 27c0bd5775f26059d615f270d9e74c36e5c55f72fba1a95de0e15f66de1eec857e8470aa62bde31cba19024f80a3cf8e8b487582703f142b3c167eb02b0a0e86 @@ -0,0 +1,103 @@ +/* memory.h - memory allocation + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#ifndef G10_MEMORY_H +#define G10_MEMORY_H + +#ifdef M_DEBUG + +#ifndef STR +#define STR(v) #v +#endif + +#define M_DBGINFO(a) __FUNCTION__ "["__FILE__ ":" STR(a) "]" + +#define xmalloc(n) m_debug_alloc((n), M_DBGINFO( __LINE__ ) ) +#define xtrymalloc(n) m_debug_trymalloc ((n), M_DBGINFO( __LINE__ )) +#define xmalloc_clear(n) m_debug_alloc_clear((n), M_DBGINFO(__LINE__) ) +#define xmalloc_secure(n) m_debug_alloc_secure(n), M_DBGINFO(__LINE__) ) +#define xmalloc_secure_clear(n) m_debug_alloc_secure_clear((n), M_DBGINFO(__LINE__) ) +#define xrealloc(n,m) m_debug_realloc((n),(m), M_DBGINFO(__LINE__) ) +#define xfree(n) m_debug_free((n), M_DBGINFO(__LINE__) ) +#define m_check(n) m_debug_check((n), M_DBGINFO(__LINE__) ) +/*#define m_copy(a) m_debug_copy((a), M_DBGINFO(__LINE__) )*/ +#define xstrdup(a) m_debug_strdup((a), M_DBGINFO(__LINE__) ) +#define xtrystrdup(a) m_debug_trystrdup((a), M_DBGINFO(__LINE__) ) + +void *m_debug_alloc( size_t n, const char *info ); +void *m_debug_trymalloc (size_t n, const char *info); +void *m_debug_alloc_clear( size_t n, const char *info ); +void *m_debug_alloc_secure( size_t n, const char *info ); +void *m_debug_alloc_secure_clear( size_t n, const char *info ); +void *m_debug_realloc( void *a, size_t n, const char *info ); +void m_debug_free( void *p, const char *info ); +void m_debug_check( const void *a, const char *info ); +/*void *m_debug_copy( const void *a, const char *info );*/ +char *m_debug_strdup( const char *a, const char *info ); +char *m_debug_trystrdup (const char *a, const char *info); + +#else +void *xmalloc( size_t n ); +void *xtrymalloc (size_t n); +void *xmalloc_clear( size_t n ); +void *xmalloc_secure( size_t n ); +void *xmalloc_secure_clear( size_t n ); +void *xrealloc( void *a, size_t n ); +void xfree( void *p ); +void m_check( const void *a ); +/*void *m_copy( const void *a );*/ +char *xstrdup( const char * a); +char *xtrystrdup (const char *a); +#endif + +size_t m_size( const void *a ); +void m_print_stats(const char *prefix); + +/* The follwing functions should be preferred over xmalloc_clear. */ +void *xcalloc (size_t n, size_t m); +void *xcalloc_secure (size_t n, size_t m); + + +/*-- secmem.c --*/ +int secmem_init( size_t npool ); +void secmem_term( void ); +void *secmem_malloc( size_t size ); +void *secmexrealloc( void *a, size_t newsize ); +void secmem_free( void *a ); +int m_is_secure( const void *p ); +void secmem_dump_stats(void); +void secmem_set_flags( unsigned flags ); +unsigned secmem_get_flags(void); + + +#define DBG_MEMORY memory_debug_mode +#define DBG_MEMSTAT memory_stat_debug_mode + +#ifndef EXTERN_UNLESS_MAIN_MODULE +#define EXTERN_UNLESS_MAIN_MODULE +#endif +EXTERN_UNLESS_MAIN_MODULE int memory_debug_mode; +EXTERN_UNLESS_MAIN_MODULE int memory_stat_debug_mode; + + + +#endif /*G10_MEMORY_H*/ diff -uNr a/eucrypt/mpi/include/mpi-inline.h b/eucrypt/mpi/include/mpi-inline.h --- a/eucrypt/mpi/include/mpi-inline.h false +++ b/eucrypt/mpi/include/mpi-inline.h 2ea77d3e9c3d040649368883bdcaeca474685ef6968e358cdd744647292902e584e34949caba771cb43145f3ac1fce64932cf2e7d48ad514b84ee81fe5492c58 @@ -0,0 +1,121 @@ +/* mpi-inline.h - Internal to the Multi Precision Integers + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#ifndef G10_MPI_INLINE_H +#define G10_MPI_INLINE_H + +#ifndef G10_MPI_INLINE_DECL +#define G10_MPI_INLINE_DECL extern __inline__ +#endif + +G10_MPI_INLINE_DECL mpi_limb_t +mpihelp_add_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_size_t s1_size, mpi_limb_t s2_limb) +{ + mpi_limb_t x; + + x = *s1_ptr++; + s2_limb += x; + *res_ptr++ = s2_limb; + if( s2_limb < x ) { /* sum is less than the left operand: handle carry */ + while( --s1_size ) { + x = *s1_ptr++ + 1; /* add carry */ + *res_ptr++ = x; /* and store */ + if( x ) /* not 0 (no overflow): we can stop */ + goto leave; + } + return 1; /* return carry (size of s1 to small) */ + } + + leave: + if( res_ptr != s1_ptr ) { /* not the same variable */ + mpi_size_t i; /* copy the rest */ + for( i=0; i < s1_size-1; i++ ) + res_ptr[i] = s1_ptr[i]; + } + return 0; /* no carry */ +} + + + +G10_MPI_INLINE_DECL mpi_limb_t +mpihelp_add(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size, + mpi_ptr_t s2_ptr, mpi_size_t s2_size) +{ + mpi_limb_t cy = 0; + + if( s2_size ) + cy = mpihelp_add_n( res_ptr, s1_ptr, s2_ptr, s2_size ); + + if( s1_size - s2_size ) + cy = mpihelp_add_1( res_ptr + s2_size, s1_ptr + s2_size, + s1_size - s2_size, cy); + return cy; +} + + +G10_MPI_INLINE_DECL mpi_limb_t +mpihelp_sub_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_size_t s1_size, mpi_limb_t s2_limb ) +{ + mpi_limb_t x; + + x = *s1_ptr++; + s2_limb = x - s2_limb; + *res_ptr++ = s2_limb; + if( s2_limb > x ) { + while( --s1_size ) { + x = *s1_ptr++; + *res_ptr++ = x - 1; + if( x ) + goto leave; + } + return 1; + } + + leave: + if( res_ptr != s1_ptr ) { + mpi_size_t i; + for( i=0; i < s1_size-1; i++ ) + res_ptr[i] = s1_ptr[i]; + } + return 0; +} + + + +G10_MPI_INLINE_DECL mpi_limb_t +mpihelp_sub( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size, + mpi_ptr_t s2_ptr, mpi_size_t s2_size) +{ + mpi_limb_t cy = 0; + + if( s2_size ) + cy = mpihelp_sub_n(res_ptr, s1_ptr, s2_ptr, s2_size); + + if( s1_size - s2_size ) + cy = mpihelp_sub_1(res_ptr + s2_size, s1_ptr + s2_size, + s1_size - s2_size, cy); + return cy; +} + +#endif /*G10_MPI_INLINE_H*/ diff -uNr a/eucrypt/mpi/include/mpi-internal.h b/eucrypt/mpi/include/mpi-internal.h --- a/eucrypt/mpi/include/mpi-internal.h false +++ b/eucrypt/mpi/include/mpi-internal.h 4c06fe251cb2613489112e141996aacc96df8663971921487aa423f35648f26b8c57eaebb4c392196ef382778c6150b5d73921aaafc3ed3cd65216f4eb6c1cf0 @@ -0,0 +1,286 @@ +/* mpi-internal.h - Internal to the Multi Precision Integers + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#ifndef G10_MPI_INTERNAL_H +#define G10_MPI_INTERNAL_H + +#include "mpi.h" + +/* from the old mpi-asm-defs.h */ +#define BYTES_PER_MPI_LIMB (SIZEOF_UNSIGNED_LONG) + +#if BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_INT + typedef unsigned int mpi_limb_t; + typedef signed int mpi_limb_signed_t; +#elif BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_LONG + typedef unsigned long int mpi_limb_t; + typedef signed long int mpi_limb_signed_t; +#elif BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_LONG_LONG + typedef unsigned long long int mpi_limb_t; + typedef signed long long int mpi_limb_signed_t; +#elif BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_SHORT + typedef unsigned short int mpi_limb_t; + typedef signed short int mpi_limb_signed_t; +#else +#error BYTES_PER_MPI_LIMB does not match any C type +#endif +#define BITS_PER_MPI_LIMB (8*BYTES_PER_MPI_LIMB) + + +struct gcry_mpi { + int alloced; /* array size (# of allocated limbs) */ + int nlimbs; /* number of valid limbs */ + unsigned int nbits; /* the real number of valid bits (info only) */ + int sign; /* indicates a negative number */ + unsigned flags; /* bit 0: array must be allocated in secure memory space */ + /* bit 1: not used */ + /* bit 2: the limb is a pointer to some xmalloced data */ + mpi_limb_t *d; /* array with the limbs */ +}; + + + +/* If KARATSUBA_THRESHOLD is not already defined, define it to a + * value which is good on most machines. */ + +/* tested 4, 16, 32 and 64, where 16 gave the best performance when + * checking a 768 and a 1024 bit ElGamal signature. + * (wk 22.12.97) */ +#ifndef KARATSUBA_THRESHOLD +#define KARATSUBA_THRESHOLD 16 +#endif + +/* The code can't handle KARATSUBA_THRESHOLD smaller than 2. */ +#if KARATSUBA_THRESHOLD < 2 +#undef KARATSUBA_THRESHOLD +#define KARATSUBA_THRESHOLD 2 +#endif + + +typedef mpi_limb_t *mpi_ptr_t; /* pointer to a limb */ +typedef int mpi_size_t; /* (must be a signed type) */ + +#define ABS(x) (x >= 0 ? x : -x) +#define MIN(l,o) ((l) < (o) ? (l) : (o)) +#define MAX(h,i) ((h) > (i) ? (h) : (i)) +#define RESIZE_IF_NEEDED(a,b) \ + do { \ + if( (a)->alloced < (b) ) \ + mpi_resize((a), (b)); \ + } while(0) + +/* Copy N limbs from S to D. */ +#define MPN_COPY( d, s, n) \ + do { \ + mpi_size_t _i; \ + for( _i = 0; _i < (n); _i++ ) \ + (d)[_i] = (s)[_i]; \ + } while(0) + +#define MPN_COPY_INCR( d, s, n) \ + do { \ + mpi_size_t _i; \ + for( _i = 0; _i < (n); _i++ ) \ + (d)[_i] = (d)[_i]; \ + } while (0) + +#define MPN_COPY_DECR( d, s, n ) \ + do { \ + mpi_size_t _i; \ + for( _i = (n)-1; _i >= 0; _i--) \ + (d)[_i] = (s)[_i]; \ + } while(0) + +/* Zero N limbs at D */ +#define MPN_ZERO(d, n) \ + do { \ + int _i; \ + for( _i = 0; _i < (n); _i++ ) \ + (d)[_i] = 0; \ + } while (0) + +#define MPN_NORMALIZE(d, n) \ + do { \ + while( (n) > 0 ) { \ + if( (d)[(n)-1] ) \ + break; \ + (n)--; \ + } \ + } while(0) + +#define MPN_NORMALIZE_NOT_ZERO(d, n) \ + do { \ + for(;;) { \ + if( (d)[(n)-1] ) \ + break; \ + (n)--; \ + } \ + } while(0) + +#define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \ + do { \ + if( (size) < KARATSUBA_THRESHOLD ) \ + mul_n_basecase (prodp, up, vp, size); \ + else \ + mul_n (prodp, up, vp, size, tspace); \ + } while (0); + + +/* Divide the two-limb number in (NH,,NL) by D, with DI being the largest + * limb not larger than (2**(2*BITS_PER_MP_LIMB))/D - (2**BITS_PER_MP_LIMB). + * If this would yield overflow, DI should be the largest possible number + * (i.e., only ones). For correct operation, the most significant bit of D + * has to be set. Put the quotient in Q and the remainder in R. + */ +#define UDIV_QRNND_PREINV(q, r, nh, nl, d, di) \ + do { \ + mpi_limb_t _q, _ql, _r; \ + mpi_limb_t _xh, _xl; \ + umul_ppmm (_q, _ql, (nh), (di)); \ + _q += (nh); /* DI is 2**BITS_PER_MPI_LIMB too small */ \ + umul_ppmm (_xh, _xl, _q, (d)); \ + sub_ddmmss (_xh, _r, (nh), (nl), _xh, _xl); \ + if( _xh ) { \ + sub_ddmmss (_xh, _r, _xh, _r, 0, (d)); \ + _q++; \ + if( _xh) { \ + sub_ddmmss (_xh, _r, _xh, _r, 0, (d)); \ + _q++; \ + } \ + } \ + if( _r >= (d) ) { \ + _r -= (d); \ + _q++; \ + } \ + (r) = _r; \ + (q) = _q; \ + } while (0) + + +/*-- mpiutil.c --*/ +#ifdef M_DEBUG +#define mpi_alloc_limb_space(n,f) mpi_debug_alloc_limb_space((n),(f), M_DBGINFO( __LINE__ ) ) +#define mpi_free_limb_space(n) mpi_debug_free_limb_space((n), M_DBGINFO( __LINE__ ) ) + mpi_ptr_t mpi_debug_alloc_limb_space( unsigned nlimbs, int sec, const char *info ); + void mpi_debug_free_limb_space( mpi_ptr_t a, const char *info ); +#else + mpi_ptr_t mpi_alloc_limb_space( unsigned nlimbs, int sec ); + void mpi_free_limb_space( mpi_ptr_t a ); +#endif +void mpi_assign_limb_space( MPI a, mpi_ptr_t ap, unsigned nlimbs ); + +/*-- mpi-bit.c --*/ +void mpi_rshift_limbs( MPI a, unsigned int count ); +void mpi_lshift_limbs( MPI a, unsigned int count ); + + +/*-- mpihelp-add.c --*/ +mpi_limb_t mpihelp_add_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_size_t s1_size, mpi_limb_t s2_limb ); +mpi_limb_t mpihelp_add_n( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_ptr_t s2_ptr, mpi_size_t size); +mpi_limb_t mpihelp_add(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size, + mpi_ptr_t s2_ptr, mpi_size_t s2_size); + +/*-- mpihelp-sub.c --*/ +mpi_limb_t mpihelp_sub_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_size_t s1_size, mpi_limb_t s2_limb ); +mpi_limb_t mpihelp_sub_n( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_ptr_t s2_ptr, mpi_size_t size); +mpi_limb_t mpihelp_sub(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size, + mpi_ptr_t s2_ptr, mpi_size_t s2_size); + +/*-- mpihelp-cmp.c --*/ +int mpihelp_cmp( mpi_ptr_t op1_ptr, mpi_ptr_t op2_ptr, mpi_size_t size ); + +/*-- mpihelp-mul.c --*/ + +struct karatsuba_ctx { + struct karatsuba_ctx *next; + mpi_ptr_t tspace; + mpi_size_t tspace_size; + mpi_ptr_t tp; + mpi_size_t tp_size; +}; + +void mpihelp_release_karatsuba_ctx( struct karatsuba_ctx *ctx ); + +mpi_limb_t mpihelp_addmul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_size_t s1_size, mpi_limb_t s2_limb); +mpi_limb_t mpihelp_submul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_size_t s1_size, mpi_limb_t s2_limb); +void mpihelp_mul_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp, + mpi_size_t size); +mpi_limb_t mpihelp_mul( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize, + mpi_ptr_t vp, mpi_size_t vsize); +void mpih_sqr_n_basecase( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size ); +void mpih_sqr_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size, + mpi_ptr_t tspace); + +void mpihelp_mul_karatsuba_case( mpi_ptr_t prodp, + mpi_ptr_t up, mpi_size_t usize, + mpi_ptr_t vp, mpi_size_t vsize, + struct karatsuba_ctx *ctx ); + + +/*-- mpihelp-mul_1.c (or xxx/cpu/ *.S) --*/ +mpi_limb_t mpihelp_mul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_size_t s1_size, mpi_limb_t s2_limb); + +/*-- mpihelp-div.c --*/ +mpi_limb_t mpihelp_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size, + mpi_limb_t divisor_limb); +mpi_limb_t mpihelp_divrem( mpi_ptr_t qp, mpi_size_t qextra_limbs, + mpi_ptr_t np, mpi_size_t nsize, + mpi_ptr_t dp, mpi_size_t dsize); +mpi_limb_t mpihelp_divmod_1( mpi_ptr_t quot_ptr, + mpi_ptr_t dividend_ptr, mpi_size_t dividend_size, + mpi_limb_t divisor_limb); + +/*-- mpihelp-shift.c --*/ +mpi_limb_t mpihelp_lshift( mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, + unsigned cnt); +mpi_limb_t mpihelp_rshift( mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, + unsigned cnt); + + +/* Define stuff for longlong.h. */ +#define W_TYPE_SIZE BITS_PER_MPI_LIMB + typedef mpi_limb_t UWtype; + typedef unsigned int UHWtype; +#if defined (__GNUC__) + typedef unsigned int UQItype __attribute__ ((mode (QI))); + typedef int SItype __attribute__ ((mode (SI))); + typedef unsigned int USItype __attribute__ ((mode (SI))); + typedef int DItype __attribute__ ((mode (DI))); + typedef unsigned int UDItype __attribute__ ((mode (DI))); +#else + typedef unsigned char UQItype; + typedef long SItype; + typedef unsigned long USItype; +#endif + +#ifdef __GNUC__ +#include "mpi-inline.h" +#endif + +#endif /*G10_MPI_INTERNAL_H*/ diff -uNr a/eucrypt/mpi/include/mpi.h b/eucrypt/mpi/include/mpi.h --- a/eucrypt/mpi/include/mpi.h false +++ b/eucrypt/mpi/include/mpi.h 295ff95b636878675cdc74b113ee282afb19cabcae79fda85e80de853604148265e1d150697eaa9aa727b02bc4ace33d98c2242fa4122107cd3f5b0dbf3b6bb8 @@ -0,0 +1,150 @@ +/* mpi.h - Multi Precision Integers + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#ifndef G10_MPI_H +#define G10_MPI_H + +#include +#include "knobs.h" +#include "types.h" +#include "memory.h" + +#ifndef EXTERN_UNLESS_MAIN_MODULE +#define EXTERN_UNLESS_MAIN_MODULE +#endif + +#define DBG_MPI mpi_debug_mode +EXTERN_UNLESS_MAIN_MODULE int mpi_debug_mode; + + +struct gcry_mpi; +typedef struct gcry_mpi *MPI; + + +/*-- mpiutil.c --*/ + +#ifdef M_DEBUG +#define mpi_alloc(n) mpi_debug_alloc((n), M_DBGINFO( __LINE__ ) ) +#define mpi_alloc_secure(n) mpi_debug_alloc_secure((n), M_DBGINFO( __LINE__ ) ) +#define mpi_alloc_like(n) mpi_debug_alloc_like((n), M_DBGINFO( __LINE__ ) ) +#define mpi_free(a) mpi_debug_free((a), M_DBGINFO(__LINE__) ) +#define mpi_resize(a,b) mpi_debug_resize((a),(b), M_DBGINFO(__LINE__) ) +#define mpi_copy(a) mpi_debug_copy((a), M_DBGINFO(__LINE__) ) +MPI mpi_debug_alloc( unsigned nlimbs, const char *info ); +MPI mpi_debug_alloc_secure( unsigned nlimbs, const char *info ); +MPI mpi_debug_alloc_like( MPI a, const char *info ); +void mpi_debug_free( MPI a, const char *info ); +void mpi_debug_resize( MPI a, unsigned nlimbs, const char *info ); +MPI mpi_debug_copy( MPI a, const char *info ); +#else +MPI mpi_alloc( unsigned nlimbs ); +MPI mpi_alloc_secure( unsigned nlimbs ); +MPI mpi_alloc_like( MPI a ); +void mpi_free( MPI a ); +void mpi_resize( MPI a, unsigned nlimbs ); +MPI mpi_copy( MPI a ); +#endif +#define mpi_is_opaque(a) ((a) && (mpi_get_flags (a)&4)) +MPI mpi_set_opaque( MPI a, void *p, unsigned int len ); +void *mpi_get_opaque( MPI a, unsigned int *len ); +#define mpi_is_secure(a) ((a) && (mpi_get_flags (a)&1)) +void mpi_set_secure( MPI a ); +void mpi_clear( MPI a ); +void mpi_set( MPI w, MPI u); +void mpi_set_ui( MPI w, ulong u); +MPI mpi_alloc_set_ui( unsigned long u); +void mpi_m_check( MPI a ); +void mpi_swap( MPI a, MPI b); +int mpi_get_nlimbs (MPI a); +int mpi_is_neg (MPI a); +unsigned int mpi_nlimb_hint_from_nbytes (unsigned int nbytes); +unsigned int mpi_nlimb_hint_from_nbits (unsigned int nbits); +unsigned int mpi_get_flags (MPI a); + +/*-- mpicoder.c --*/ +MPI mpi_read_from_buffer(byte *buffer, unsigned *ret_nread, int secure); +int mpi_fromstr(MPI val, const char *str); +int mpi_print( FILE *fp, MPI a, int mode ); +//void g10_log_mpidump( const char *text, MPI a ); +byte *mpi_get_buffer( MPI a, unsigned *nbytes, int *sign ); +byte *mpi_get_secure_buffer( MPI a, unsigned *nbytes, int *sign ); +void mpi_set_buffer( MPI a, const byte *buffer, unsigned nbytes, int sign ); + +#define log_mpidump g10_log_mpidump + +/*-- mpi-add.c --*/ +void mpi_add_ui(MPI w, MPI u, ulong v ); +void mpi_add(MPI w, MPI u, MPI v); +void mpi_addm(MPI w, MPI u, MPI v, MPI m); +void mpi_sub_ui(MPI w, MPI u, ulong v ); +void mpi_sub( MPI w, MPI u, MPI v); +void mpi_subm( MPI w, MPI u, MPI v, MPI m); + +/*-- mpi-mul.c --*/ +void mpi_mul_ui(MPI w, MPI u, ulong v ); +void mpi_mul_2exp( MPI w, MPI u, ulong cnt); +void mpi_mul( MPI w, MPI u, MPI v); +void mpi_mulm( MPI w, MPI u, MPI v, MPI m); + +/*-- mpi-div.c --*/ +ulong mpi_fdiv_r_ui( MPI rem, MPI dividend, ulong divisor ); +void mpi_fdiv_r( MPI rem, MPI dividend, MPI divisor ); +void mpi_fdiv_q( MPI quot, MPI dividend, MPI divisor ); +void mpi_fdiv_qr( MPI quot, MPI rem, MPI dividend, MPI divisor ); +void mpi_tdiv_r( MPI rem, MPI num, MPI den); +void mpi_tdiv_qr( MPI quot, MPI rem, MPI num, MPI den); +void mpi_tdiv_q_2exp( MPI w, MPI u, unsigned count ); +int mpi_divisible_ui(MPI dividend, ulong divisor ); + +/*-- mpi-gcd.c --*/ +int mpi_gcd( MPI g, MPI a, MPI b ); + +/*-- mpi-pow.c --*/ +void mpi_pow( MPI w, MPI u, MPI v); +void mpi_powm( MPI res, MPI base, MPI exponent, MPI mod); + +/*-- mpi-mpow.c --*/ +void mpi_mulpowm( MPI res, MPI *basearray, MPI *exparray, MPI mod); + +/*-- mpi-cmp.c --*/ +int mpi_cmp_ui( MPI u, ulong v ); +int mpi_cmp( MPI u, MPI v ); + +/*-- mpi-scan.c --*/ +int mpi_getbyte( MPI a, unsigned idx ); +void mpi_putbyte( MPI a, unsigned idx, int value ); +unsigned mpi_trailing_zeros( MPI a ); + +/*-- mpi-bit.c --*/ +void mpi_normalize( MPI a ); +unsigned mpi_get_nbits( MPI a ); +int mpi_test_bit( MPI a, unsigned n ); +void mpi_set_bit( MPI a, unsigned n ); +void mpi_set_highbit( MPI a, unsigned n ); +void mpi_clear_highbit( MPI a, unsigned n ); +void mpi_clear_bit( MPI a, unsigned n ); +void mpi_rshift( MPI x, MPI a, unsigned n ); + +/*-- mpi-inv.c --*/ +void mpi_invm( MPI x, MPI u, MPI v ); + +#endif /*G10_MPI_H*/ diff -uNr a/eucrypt/mpi/include/types.h b/eucrypt/mpi/include/types.h --- a/eucrypt/mpi/include/types.h false +++ b/eucrypt/mpi/include/types.h fab4d9725d153347b3e67dcbc53ed25f5f8cd8149d35b17f11ce06cd62a825368f95b95f65f394395cebe34baa02afd4f0b331d3019ba6e8b0db73a947a7878a @@ -0,0 +1,138 @@ +/* types.h - some common typedefs + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#ifndef G10_TYPES_H +#define G10_TYPES_H + +#ifdef HAVE_INTTYPES_H +/* For uint64_t */ +#include +#endif + +/* The AC_CHECK_SIZEOF() in configure fails for some machines. + * we provide some fallback values here */ +#if !SIZEOF_UNSIGNED_SHORT +#undef SIZEOF_UNSIGNED_SHORT +#define SIZEOF_UNSIGNED_SHORT 2 +#endif +#if !SIZEOF_UNSIGNED_INT +#undef SIZEOF_UNSIGNED_INT +#define SIZEOF_UNSIGNED_INT 4 +#endif +#if !SIZEOF_UNSIGNED_LONG +#undef SIZEOF_UNSIGNED_LONG +#define SIZEOF_UNSIGNED_LONG 4 +#endif + + +#include + + +#ifndef HAVE_BYTE_TYPEDEF +#undef byte /* maybe there is a macro with this name */ +typedef unsigned char byte; +#define HAVE_BYTE_TYPEDEF +#endif + +#ifndef HAVE_USHORT_TYPEDEF +#undef ushort /* maybe there is a macro with this name */ +typedef unsigned short ushort; +#define HAVE_USHORT_TYPEDEF +#endif + +#ifndef HAVE_ULONG_TYPEDEF +#undef ulong /* maybe there is a macro with this name */ +typedef unsigned long ulong; +#define HAVE_ULONG_TYPEDEF +#endif + +#ifndef HAVE_U16_TYPEDEF +#undef u16 /* maybe there is a macro with this name */ +#if SIZEOF_UNSIGNED_INT == 2 +typedef unsigned int u16; +#elif SIZEOF_UNSIGNED_SHORT == 2 +typedef unsigned short u16; +#else +#error no typedef for u16 +#endif +#define HAVE_U16_TYPEDEF +#endif + +#ifndef HAVE_U32_TYPEDEF +#undef u32 /* maybe there is a macro with this name */ +#if SIZEOF_UNSIGNED_INT == 4 +typedef unsigned int u32; +#elif SIZEOF_UNSIGNED_LONG == 4 +typedef unsigned long u32; +#else +#error no typedef for u32 +#endif +#define HAVE_U32_TYPEDEF +#endif + +/**************** + * Warning: Some systems segfault when this u64 typedef and + * the dummy code in cipher/md.c is not available. Examples are + * Solaris and IRIX. + */ +#ifndef HAVE_U64_TYPEDEF +#undef u64 /* maybe there is a macro with this name */ +#if SIZEOF_UINT64_T == 8 +typedef uint64_t u64; +#define U64_C(c) (UINT64_C(c)) +#define HAVE_U64_TYPEDEF +#elif SIZEOF_UNSIGNED_INT == 8 +typedef unsigned int u64; +#define U64_C(c) (c ## U) +#define HAVE_U64_TYPEDEF +#elif SIZEOF_UNSIGNED_LONG == 8 +typedef unsigned long u64; +#define U64_C(c) (c ## UL) +#define HAVE_U64_TYPEDEF +#elif SIZEOF_UNSIGNED_LONG_LONG == 8 +typedef unsigned long long u64; +#define U64_C(c) (c ## ULL) +#define HAVE_U64_TYPEDEF +#endif +#endif + +typedef union { + int a; + short b; + char c[1]; + long d; +#ifdef HAVE_U64_TYPEDEF + u64 e; +#endif + float f; + double g; +} PROPERLY_ALIGNED_TYPE; + +struct string_list { + struct string_list *next; + unsigned int flags; + char d[1]; +}; +typedef struct string_list *STRLIST; +typedef struct string_list *strlist_t; + +#endif /*G10_TYPES_H*/ diff -uNr a/eucrypt/mpi/include/util.h b/eucrypt/mpi/include/util.h --- a/eucrypt/mpi/include/util.h false +++ b/eucrypt/mpi/include/util.h 9cb4e6a599501ccb7615c4da88439d29c483b03d85ba4fc5a02c2b2fbf2920aede4e99f0438d86802183b05f3a113ca597a676b18d373f2d5e39d9d6f65553b2 @@ -0,0 +1,86 @@ +/* util.h + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#ifndef G10_UTIL_H +#define G10_UTIL_H + +#if defined (_WIN32) || defined (__CYGWIN32__) +#include +#endif + +#include "types.h" +#include "types.h" +#include "mpi.h" + +#define log_hexdump printf +#define log_bug printf +#define log_bug0 printf +#define log_fatal printf +#define log_error printf +#define log_info printf +#define log_warning printf +#define log_debug printf + +#define g10_log_print_prefix printf + + +#ifndef HAVE_MEMMOVE +#define memmove(d, s, n) bcopy((s), (d), (n)) +#endif + + +/**** other missing stuff ****/ +#ifndef HAVE_ATEXIT /* For SunOS */ +#define atexit(a) (on_exit((a),0)) +#endif + +#ifndef HAVE_RAISE +#define raise(a) kill(getpid(), (a)) +#endif + +/******** some macros ************/ +#ifndef STR +#define STR(v) #v +#endif +#define STR2(v) STR(v) +#define DIM(v) (sizeof(v)/sizeof((v)[0])) +#define DIMof(type,member) DIM(((type *)0)->member) + +#define wipememory2(_ptr,_set,_len) do { volatile char *_vptr=(volatile char *)(_ptr); size_t _vlen=(_len); while(_vlen) { *_vptr=(_set); _vptr++; _vlen--; } } while(0) +#define wipememory(_ptr,_len) wipememory2(_ptr,0,_len) + +/*-- macros to replace ctype ones and avoid locale problems --*/ +#define spacep(p) (*(p) == ' ' || *(p) == '\t') +#define digitp(p) (*(p) >= '0' && *(p) <= '9') +#define hexdigitp(a) (digitp (a) \ + || (*(a) >= 'A' && *(a) <= 'F') \ + || (*(a) >= 'a' && *(a) <= 'f')) +/* the atoi macros assume that the buffer has only valid digits */ +#define atoi_1(p) (*(p) - '0' ) +#define atoi_2(p) ((atoi_1(p) * 10) + atoi_1((p)+1)) +#define atoi_4(p) ((atoi_2(p) * 100) + atoi_2((p)+2)) +#define xtoi_1(p) (*(p) <= '9'? (*(p)- '0'): \ + *(p) <= 'F'? (*(p)-'A'+10):(*(p)-'a'+10)) +#define xtoi_2(p) ((xtoi_1(p) * 16) + xtoi_1((p)+1)) + + +#endif /*G10_UTIL_H*/ diff -uNr a/eucrypt/mpi/memory.c b/eucrypt/mpi/memory.c --- a/eucrypt/mpi/memory.c false +++ b/eucrypt/mpi/memory.c 739f6960d138e5ab2eb53f41872bef6de1a66ee43161b6b8a69d12849f13332e48db2392566a8736d6b2bf7272dfc01aa2bfe927d917f152be75ae821de1afd6 @@ -0,0 +1,671 @@ +/* memory.c - memory allocation + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +/* We use our own memory allocation functions instead of plain malloc(), + * so that we can provide some special enhancements: + * a) functions to provide memory from a secure memory. + * b) by looking at the requested allocation size we + * can reuse memory very quickly (e.g. MPI storage) + * (really needed?) + * c) memory usage reporting if compiled with M_DEBUG + * d) memory checking if compiled with M_GUARD + */ + +#include +#include +#include +#include + +#include "knobs.h" +#include "types.h" +#include "memory.h" +#include "util.h" + +#define MAGIC_NOR_BYTE 0x55 +#define MAGIC_SEC_BYTE 0xcc +#define MAGIC_END_BYTE 0xaa + +/* This is a very crude alignment check which does not work on all CPUs + * IIRC, I once introduced it for testing on an Alpha. We should better + * replace this guard stuff with one provided by a modern malloc library + */ +#if SIZEOF_UNSIGNED_LONG == 8 +#define EXTRA_ALIGN 4 +#else +#define EXTRA_ALIGN 0 +#endif + +#if defined(M_DEBUG) || defined(M_GUARD) + static void membug( const char *fmt, ... ); +#endif + +#ifdef M_DEBUG + +#ifndef M_GUARD +#define M_GUARD 1 +#endif +#undef xmalloc +#undef xtrymalloc +#undef xmalloc_clear +#undef xmalloc_secure +#undef xmalloc_secure_clear +#undef xrealloc +#undef xfree +#undef m_check +#undef xstrdup +#undef xtrystrdup +#define FNAME(a) m_debug_ ##a +#define FNAMEX(a) m_debug_ ##a +#define FNAMEXM(a) m_debug_ ##a +#define FNAMEPRT , const char *info +#define FNAMEARG , info + +#define store_len(p,n,m) do { add_entry(p,n,m, \ + info, __FUNCTION__); } while(0) +#else +#define FNAME(a) m_ ##a +#define FNAMEX(a) x ##a +#define FNAMEXM(a) xm ##a +#define FNAMEPRT +#define FNAMEARG +#define store_len(p,n,m) do { ((byte*)p)[EXTRA_ALIGN+0] = n; \ + ((byte*)p)[EXTRA_ALIGN+1] = n >> 8 ; \ + ((byte*)p)[EXTRA_ALIGN+2] = n >> 16 ; \ + ((byte*)p)[EXTRA_ALIGN+3] = m? MAGIC_SEC_BYTE \ + : MAGIC_NOR_BYTE; \ + } while(0) +#endif + + +#ifdef M_GUARD +static long used_memory; +#endif + +#ifdef M_DEBUG /* stuff used for memory debuging */ + +struct info_entry { + struct info_entry *next; + unsigned count; /* call count */ + const char *info; /* the reference to the info string */ +}; + +struct memtbl_entry { + const void *user_p; /* for reference: the pointer given to the user */ + size_t user_n; /* length requested by the user */ + struct memtbl_entry *next; /* to build a list of unused entries */ + const struct info_entry *info; /* points into the table with */ + /* the info strings */ + unsigned inuse:1; /* this entry is in use */ + unsigned count:31; +}; + + +#define INFO_BUCKETS 53 +#define info_hash(p) ( *(u32*)((p)) % INFO_BUCKETS ) +static struct info_entry *info_strings[INFO_BUCKETS]; /* hash table */ + +static struct memtbl_entry *memtbl; /* the table with the memory info */ +static unsigned memtbl_size; /* number of allocated entries */ +static unsigned memtbl_len; /* number of used entries */ +static struct memtbl_entry *memtbl_unused;/* to keep track of unused entries */ + +static void dump_table_at_exit(void); +static void dump_table(void); +static void check_allmem( const char *info ); + +/**************** + * Put the new P into the debug table and return a pointer to the table entry. + * mode is true for security. BY is the name of the function which called us. + */ +static void +add_entry( byte *p, unsigned n, int mode, const char *info, const char *by ) +{ + unsigned index; + struct memtbl_entry *e; + struct info_entry *ie; + + if( memtbl_len < memtbl_size ) + index = memtbl_len++; + else { + struct memtbl_entry *e; + /* look for a used entry in the table. We take the first one, + * so that freed entries remain as long as possible in the table + * (free appends a new one) + */ + if( (e = memtbl_unused) ) { + index = e - memtbl; + memtbl_unused = e->next; + e->next = NULL; + } + else { /* no free entries in the table: extend the table */ + if( !memtbl_size ) { /* first time */ + memtbl_size = 100; + if( !(memtbl = calloc( memtbl_size, sizeof *memtbl )) ) + membug("memory debug table malloc failed\n"); + index = 0; + memtbl_len = 1; + atexit( dump_table_at_exit ); + } + else { /* realloc */ + unsigned n = memtbl_size / 4; /* enlarge by 25% */ + if(!(memtbl = realloc(memtbl, (memtbl_size+n)*sizeof *memtbl))) + membug("memory debug table realloc failed\n"); + memset(memtbl+memtbl_size, 0, n*sizeof *memtbl ); + memtbl_size += n; + index = memtbl_len++; + } + } + } + e = memtbl+index; + if( e->inuse ) + membug("Ooops: entry %u is flagged as in use\n", index); + e->user_p = p + EXTRA_ALIGN + 4; + e->user_n = n; + e->count++; + if( e->next ) + membug("Ooops: entry is in free entry list\n"); + /* do we already have this info string */ + for( ie = info_strings[info_hash(info)]; ie; ie = ie->next ) + if( ie->info == info ) + break; + if( !ie ) { /* no: make a new entry */ + if( !(ie = malloc( sizeof *ie )) ) + membug("can't allocate info entry\n"); + ie->next = info_strings[info_hash(info)]; + info_strings[info_hash(info)] = ie; + ie->info = info; + ie->count = 0; + } + ie->count++; + e->info = ie; + e->inuse = 1; + + /* put the index at the start of the memory */ + p[EXTRA_ALIGN+0] = index; + p[EXTRA_ALIGN+1] = index >> 8 ; + p[EXTRA_ALIGN+2] = index >> 16 ; + p[EXTRA_ALIGN+3] = mode? MAGIC_SEC_BYTE : MAGIC_NOR_BYTE ; + if( DBG_MEMORY ) + log_debug( "%s allocates %u bytes using %s\n", info, e->user_n, by ); +} + + + +/**************** + * Check that the memory block is correct. The magic byte has already been + * checked. Checks which are done here: + * - see whether the index points into our memory table + * - see whether P is the same as the one stored in the table + * - see whether we have already freed this block. + */ +struct memtbl_entry * +check_mem( const byte *p, const char *info ) +{ + unsigned n; + struct memtbl_entry *e; + + n = p[EXTRA_ALIGN+0]; + n |= p[EXTRA_ALIGN+1] << 8; + n |= p[EXTRA_ALIGN+2] << 16; + + if( n >= memtbl_len ) + membug("memory at %p corrupted: index=%u table_len=%u (%s)\n", + p+EXTRA_ALIGN+4, n, memtbl_len, info ); + e = memtbl+n; + + if( e->user_p != p+EXTRA_ALIGN+4 ) + membug("memory at %p corrupted: reference mismatch (%s)\n", + p+EXTRA_ALIGN+4, info ); + if( !e->inuse ) + membug("memory at %p corrupted: marked as free (%s)\n", + p+EXTRA_ALIGN+4, info ); + + if( !(p[EXTRA_ALIGN+3] == MAGIC_NOR_BYTE + || p[EXTRA_ALIGN+3] == MAGIC_SEC_BYTE) ) + membug("memory at %p corrupted: underflow=%02x (%s)\n", + p+EXTRA_ALIGN+4, p[EXTRA_ALIGN+3], info ); + if( p[EXTRA_ALIGN+4+e->user_n] != MAGIC_END_BYTE ) + membug("memory at %p corrupted: overflow=%02x (%s)\n", + p+EXTRA_ALIGN+4, p[EXTRA_ALIGN+4+e->user_n], info ); + return e; +} + + +/**************** + * free the entry and the memory (replaces free) + */ +static void +free_entry( byte *p, const char *info ) +{ + struct memtbl_entry *e, *e2; + + check_allmem("add_entry"); + + e = check_mem(p, info); + if( DBG_MEMORY ) + log_debug( "%s frees %u bytes alloced by %s\n", + info, e->user_n, e->info->info ); + if( !e->inuse ) { + if( e->user_p == p + EXTRA_ALIGN+ 4 ) + membug("freeing an already freed pointer at %p\n", p+EXTRA_ALIGN+4 ); + else + membug("freeing pointer %p which is flagged as freed\n", p+EXTRA_ALIGN+4 ); + } + + e->inuse = 0; + e->next = NULL; + if( !memtbl_unused ) + memtbl_unused = e; + else { + for(e2=memtbl_unused; e2->next; e2 = e2->next ) + ; + e2->next = e; + } + if( m_is_secure(p+EXTRA_ALIGN+4) ) + secmem_free(p); + else { + memset(p,'f', e->user_n+5); + free(p); + } +} + +static void +dump_entry(struct memtbl_entry *e ) +{ + unsigned n = e - memtbl; + + fprintf(stderr, "mem %4u%c %5u %p %5u %s (%u)\n", + n, e->inuse?'a':'u', e->count, e->user_p, e->user_n, + e->info->info, e->info->count ); + + +} + + +static void +dump_table_at_exit( void) +{ + if( DBG_MEMSTAT ) + dump_table(); +} + +static void +dump_table( void) +{ + unsigned n; + struct memtbl_entry *e; + ulong sum = 0, chunks =0; + + for( e = memtbl, n = 0; n < memtbl_len; n++, e++ ) { + if(e->inuse) { + dump_entry(e); + sum += e->user_n; + chunks++; + } + } + fprintf(stderr, " memory used: %8lu bytes in %ld chunks\n", + sum, chunks ); +} + + +static void +check_allmem( const char *info ) +{ + unsigned n; + struct memtbl_entry *e; + + for( e = memtbl, n = 0; n < memtbl_len; n++, e++ ) { + if( e->inuse ) { + check_mem(e->user_p-4-EXTRA_ALIGN, info); + } + } +} + +#endif /* M_DEBUG */ + +#if defined(M_DEBUG) || defined(M_GUARD) +static void +membug( const char *fmt, ... ) +{ + va_list arg_ptr ; + + fprintf(stderr, "\nMemory Error: " ) ; + va_start( arg_ptr, fmt ) ; + vfprintf(stderr,fmt,arg_ptr) ; + va_end(arg_ptr); + fflush(stderr); +#ifdef M_DEBUG + if( DBG_MEMSTAT ) + dump_table(); +#endif + abort(); +} +#endif + +void +m_print_stats( const char *prefix ) +{ +#ifdef M_DEBUG + unsigned n; + struct memtbl_entry *e; + ulong sum = 0, chunks =0; + + for( e = memtbl, n = 0; n < memtbl_len; n++, e++ ) { + if(e->inuse) { + sum += e->user_n; + chunks++; + } + } + + log_debug( "%s%smemstat: %8lu bytes in %ld chunks used\n", + prefix? prefix:"", prefix? ": ":"", sum, chunks ); +#elif defined(M_GUARD) + log_debug( "%s%smemstat: %8ld bytes\n", + prefix? prefix:"", prefix? ": ":"", used_memory ); +#endif +} + +void +m_dump_table( const char *prefix ) +{ +#ifdef M_DEBUG + fprintf(stderr,"Memory-Table-Dump: %s\n", prefix); + dump_table(); +#endif + m_print_stats( prefix ); +} + + +static void +out_of_core(size_t n, int secure) +{ + log_error ("out of %s memory while allocating %u bytes\n", + secure? "secure":"" ,(unsigned)n ); + if (secure) { + /*secmem_dump_stats ();*/ + log_info ("(this may be caused by too many secret keys used " + "simultaneously or due to excessive large key sizes)\n"); + } + exit(2); +} + +/**************** + * Allocate memory of size n. + * This function gives up if we do not have enough memory + */ +void * +FNAMEXM(alloc)( size_t n FNAMEPRT ) +{ + char *p; + +#ifdef M_GUARD + if(!n) + out_of_core(n,0); /* should never happen */ + if( !(p = malloc( n + EXTRA_ALIGN+5 )) ) + out_of_core(n,0); + store_len(p,n,0); + used_memory += n; + p[4+EXTRA_ALIGN+n] = MAGIC_END_BYTE; + return p+EXTRA_ALIGN+4; +#else + /* mallocing zero bytes is undefined by ISO-C, so we better make + sure that it won't happen */ + if (!n) + n = 1; + if( !(p = malloc( n )) ) + out_of_core(n,0); + return p; +#endif +} + +/* Allocate memory of size n. This function returns NULL if we do not + have enough memory. */ +void * +FNAMEX(trymalloc)(size_t n FNAMEPRT) +{ +#ifdef M_GUARD + char *p; + + if (!n) + n = 1; + p = malloc (n + EXTRA_ALIGN+5); + if (!p) + return NULL; + store_len(p,n,0); + used_memory += n; + p[4+EXTRA_ALIGN+n] = MAGIC_END_BYTE; + return p+EXTRA_ALIGN+4; +#else + /* Mallocing zero bytes is undefined by ISO-C, so we better make + sure that it won't happen. */ + return malloc (n? n: 1); +#endif +} + +/**************** + * Allocate memory of size n from the secure memory pool. + * This function gives up if we do not have enough memory + */ +void * +FNAMEXM(alloc_secure)( size_t n FNAMEPRT ) +{ + char *p; + +#ifdef M_GUARD + if(!n) + out_of_core(n,1); /* should never happen */ + if( !(p = secmem_malloc( n +EXTRA_ALIGN+ 5 )) ) + out_of_core(n,1); + store_len(p,n,1); + p[4+EXTRA_ALIGN+n] = MAGIC_END_BYTE; + return p+EXTRA_ALIGN+4; +#else + /* mallocing zero bytes is undefined by ISO-C, so we better make + sure that it won't happen */ + if (!n) + n = 1; + if( !(p = secmem_malloc( n )) ) + out_of_core(n,1); + return p; +#endif +} + +void * +FNAMEXM(alloc_clear)( size_t n FNAMEPRT ) +{ + void *p; + p = FNAMEXM(alloc)( n FNAMEARG ); + memset(p, 0, n ); + return p; +} + +void * +FNAMEXM(alloc_secure_clear)( size_t n FNAMEPRT) +{ + void *p; + p = FNAMEXM(alloc_secure)( n FNAMEARG ); + memset(p, 0, n ); + return p; +} + + +/**************** + * realloc and clear the old space + */ +void * +FNAMEX(realloc)( void *a, size_t n FNAMEPRT ) +{ + void *b; + +#ifdef M_GUARD + if( a ) { +#error "--enable-m-guard does not currently work" + unsigned char *p = a; + size_t len = m_size(a); + + if( len >= n ) /* we don't shrink for now */ + return a; + if( p[-1] == MAGIC_SEC_BYTE ) + b = FNAME(alloc_secure_clear)(n FNAMEARG); + else + b = FNAME(alloc_clear)(n FNAMEARG); + FNAME(check)(NULL FNAMEARG); + memcpy(b, a, len ); + FNAME(free)(p FNAMEARG); + } + else + b = FNAME(alloc)(n FNAMEARG); +#else + if( m_is_secure(a) ) { + if( !(b = secmexrealloc( a, n )) ) + out_of_core(n,1); + } + else { + if( !(b = realloc( a, n )) ) + out_of_core(n,0); + } +#endif + + return b; +} + + + +/**************** + * Free a pointer + */ +void +FNAMEX(free)( void *a FNAMEPRT ) +{ + byte *p = a; + + if( !p ) + return; +#ifdef M_DEBUG + free_entry(p-EXTRA_ALIGN-4, info); +#elif defined M_GUARD + m_check(p); + if( m_is_secure(a) ) + secmem_free(p-EXTRA_ALIGN-4); + else { + used_memory -= m_size(a); + free(p-EXTRA_ALIGN-4); + } +#else + if( m_is_secure(a) ) + secmem_free(p); + else + free(p); +#endif +} + + +void +FNAME(check)( const void *a FNAMEPRT ) +{ +#ifdef M_GUARD + const byte *p = a; + +#ifdef M_DEBUG + if( p ) + check_mem(p-EXTRA_ALIGN-4, info); + else + check_allmem(info); +#else + if( !p ) + return; + if( !(p[-1] == MAGIC_NOR_BYTE || p[-1] == MAGIC_SEC_BYTE) ) + membug("memory at %p corrupted (underflow=%02x)\n", p, p[-1] ); + else if( p[m_size(p)] != MAGIC_END_BYTE ) + membug("memory at %p corrupted (overflow=%02x)\n", p, p[-1] ); +#endif +#endif +} + + +size_t +m_size( const void *a ) +{ +#ifndef M_GUARD + log_debug("dummy m_size called\n"); + return 0; +#else + const byte *p = a; + size_t n; + +#ifdef M_DEBUG + n = check_mem(p-EXTRA_ALIGN-4, "m_size")->user_n; +#else + n = ((byte*)p)[-4]; + n |= ((byte*)p)[-3] << 8; + n |= ((byte*)p)[-2] << 16; +#endif + return n; +#endif +} + + +char * +FNAMEX(strdup)( const char *a FNAMEPRT ) +{ + size_t n = strlen(a); + char *p = FNAMEXM(alloc)(n+1 FNAMEARG); + strcpy(p, a); + return p; +} + +char * +FNAMEX(trystrdup)(const char *a FNAMEPRT) +{ + size_t n = strlen (a); + char *p = FNAMEX(trymalloc)(n+1 FNAMEARG); + if (p) + strcpy (p, a); + return p; +} + + +/* Wrapper around xmalloc_clear to take the usual 2 arguments of a + calloc style function. */ +void * +xcalloc (size_t n, size_t m) +{ + size_t nbytes; + + nbytes = n * m; + if (m && nbytes / m != n) + out_of_core (nbytes, 0); + return xmalloc_clear (nbytes); +} + +/* Wrapper around xmalloc_csecure_lear to take the usual 2 arguments + of a calloc style function. */ +void * +xcalloc_secure (size_t n, size_t m) +{ + size_t nbytes; + + nbytes = n * m; + if (m && nbytes / m != n) + out_of_core (nbytes, 1); + return xmalloc_secure_clear (nbytes); +} diff -uNr a/eucrypt/mpi/mpi-add.c b/eucrypt/mpi/mpi-add.c --- a/eucrypt/mpi/mpi-add.c false +++ b/eucrypt/mpi/mpi-add.c 1d6a019fd026bf2712be8e24eb9bac995524336df8ea4bf08878bda3f95a943139e68381347974feea6ddaf3748ecd837fd698875324cb16c2af13af1e54baa0 @@ -0,0 +1,240 @@ +/* mpi-add.c - MPI functions + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" + + +/**************** + * Add the unsigned integer V to the mpi-integer U and store the + * result in W. U and V may be the same. + */ +void +mpi_add_ui(MPI w, MPI u, unsigned long v ) +{ + mpi_ptr_t wp, up; + mpi_size_t usize, wsize; + int usign, wsign; + + usize = u->nlimbs; + usign = u->sign; + wsign = 0; + + /* If not space for W (and possible carry), increase space. */ + wsize = usize + 1; + if( w->alloced < wsize ) + mpi_resize(w, wsize); + + /* These must be after realloc (U may be the same as W). */ + up = u->d; + wp = w->d; + + if( !usize ) { /* simple */ + wp[0] = v; + wsize = v? 1:0; + } + else if( !usign ) { /* mpi is not negative */ + mpi_limb_t cy; + cy = mpihelp_add_1(wp, up, usize, v); + wp[usize] = cy; + wsize = usize + cy; + } + else { /* The signs are different. Need exact comparison to determine + * which operand to subtract from which. */ + if( usize == 1 && up[0] < v ) { + wp[0] = v - up[0]; + wsize = 1; + } + else { + mpihelp_sub_1(wp, up, usize, v); + /* Size can decrease with at most one limb. */ + wsize = usize - (wp[usize-1]==0); + wsign = 1; + } + } + + w->nlimbs = wsize; + w->sign = wsign; +} + + +void +mpi_add(MPI w, MPI u, MPI v) +{ + mpi_ptr_t wp, up, vp; + mpi_size_t usize, vsize, wsize; + int usign, vsign, wsign; + + if( u->nlimbs < v->nlimbs ) { /* Swap U and V. */ + usize = v->nlimbs; + usign = v->sign; + vsize = u->nlimbs; + vsign = u->sign; + wsize = usize + 1; + RESIZE_IF_NEEDED(w, wsize); + /* These must be after realloc (u or v may be the same as w). */ + up = v->d; + vp = u->d; + } + else { + usize = u->nlimbs; + usign = u->sign; + vsize = v->nlimbs; + vsign = v->sign; + wsize = usize + 1; + RESIZE_IF_NEEDED(w, wsize); + /* These must be after realloc (u or v may be the same as w). */ + up = u->d; + vp = v->d; + } + wp = w->d; + wsign = 0; + + if( !vsize ) { /* simple */ + MPN_COPY(wp, up, usize ); + wsize = usize; + wsign = usign; + } + else if( usign != vsign ) { /* different sign */ + /* This test is right since USIZE >= VSIZE */ + if( usize != vsize ) { + mpihelp_sub(wp, up, usize, vp, vsize); + wsize = usize; + MPN_NORMALIZE(wp, wsize); + wsign = usign; + } + else if( mpihelp_cmp(up, vp, usize) < 0 ) { + mpihelp_sub_n(wp, vp, up, usize); + wsize = usize; + MPN_NORMALIZE(wp, wsize); + if( !usign ) + wsign = 1; + } + else { + mpihelp_sub_n(wp, up, vp, usize); + wsize = usize; + MPN_NORMALIZE(wp, wsize); + if( usign ) + wsign = 1; + } + } + else { /* U and V have same sign. Add them. */ + mpi_limb_t cy = mpihelp_add(wp, up, usize, vp, vsize); + wp[usize] = cy; + wsize = usize + cy; + if( usign ) + wsign = 1; + } + + w->nlimbs = wsize; + w->sign = wsign; +} + + +/**************** + * Subtract the unsigned integer V from the mpi-integer U and store the + * result in W. + */ +void +mpi_sub_ui(MPI w, MPI u, unsigned long v ) +{ + mpi_ptr_t wp, up; + mpi_size_t usize, wsize; + int usign, wsign; + + usize = u->nlimbs; + usign = u->sign; + wsign = 0; + + /* If not space for W (and possible carry), increase space. */ + wsize = usize + 1; + if( w->alloced < wsize ) + mpi_resize(w, wsize); + + /* These must be after realloc (U may be the same as W). */ + up = u->d; + wp = w->d; + + if( !usize ) { /* simple */ + wp[0] = v; + wsize = v? 1:0; + wsign = 1; + } + else if( usign ) { /* mpi and v are negative */ + mpi_limb_t cy; + cy = mpihelp_add_1(wp, up, usize, v); + wp[usize] = cy; + wsize = usize + cy; + } + else { /* The signs are different. Need exact comparison to determine + * which operand to subtract from which. */ + if( usize == 1 && up[0] < v ) { + wp[0] = v - up[0]; + wsize = 1; + wsign = 1; + } + else { + mpihelp_sub_1(wp, up, usize, v); + /* Size can decrease with at most one limb. */ + wsize = usize - (wp[usize-1]==0); + } + } + + w->nlimbs = wsize; + w->sign = wsign; +} + +void +mpi_sub(MPI w, MPI u, MPI v) +{ + if( w == v ) { + MPI vv = mpi_copy(v); + vv->sign = !vv->sign; + mpi_add( w, u, vv ); + mpi_free(vv); + } + else { + /* fixme: this is not thread-save (we temp. modify v) */ + v->sign = !v->sign; + mpi_add( w, u, v ); + v->sign = !v->sign; + } +} + + +void +mpi_addm( MPI w, MPI u, MPI v, MPI m) +{ + mpi_add(w, u, v); + mpi_fdiv_r( w, w, m ); +} + +void +mpi_subm( MPI w, MPI u, MPI v, MPI m) +{ + mpi_sub(w, u, v); + mpi_fdiv_r( w, w, m ); +} + diff -uNr a/eucrypt/mpi/mpi-bit.c b/eucrypt/mpi/mpi-bit.c --- a/eucrypt/mpi/mpi-bit.c false +++ b/eucrypt/mpi/mpi-bit.c f8b433355f471b6ea164813b4927b36d389177af169f39e25c04b3a043de367a88b8f07a6fe6eb92c851b9e20fa1b8ee0d1ec25e53a9f51477914f1a38ec1d5b @@ -0,0 +1,258 @@ +/* mpi-bit.c - MPI bit level fucntions + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" +#include "longlong.h" + + +#ifdef MPI_INTERNAL_NEED_CLZ_TAB +#ifdef __STDC__ +const +#endif +unsigned char +__clz_tab[] = +{ + 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, + 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, + 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, + 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, + 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, +}; +#endif + + +#define A_LIMB_1 ((mpi_limb_t)1) + + +/**************** + * Sometimes we have MSL (most significant limbs) which are 0; + * this is for some reasons not good, so this function removes them. + */ +void +mpi_normalize( MPI a ) +{ + if( mpi_is_opaque (a) ) + return; + + for( ; a->nlimbs && !a->d[a->nlimbs-1]; a->nlimbs-- ) + ; +} + + + +/**************** + * Return the number of bits in A. + */ +unsigned +mpi_get_nbits( MPI a ) +{ + unsigned n; + + mpi_normalize( a ); + if( a->nlimbs ) { + mpi_limb_t alimb = a->d[a->nlimbs-1]; + if( alimb ) + count_leading_zeros( n, alimb ); + else + n = BITS_PER_MPI_LIMB; + n = BITS_PER_MPI_LIMB - n + (a->nlimbs-1) * BITS_PER_MPI_LIMB; + } + else + n = 0; + return n; +} + + +/**************** + * Test whether bit N is set. + */ +int +mpi_test_bit( MPI a, unsigned n ) +{ + unsigned limbno, bitno; + mpi_limb_t limb; + + limbno = n / BITS_PER_MPI_LIMB; + bitno = n % BITS_PER_MPI_LIMB; + + if( limbno >= a->nlimbs ) + return 0; /* too far left: this is a 0 */ + limb = a->d[limbno]; + return (limb & (A_LIMB_1 << bitno))? 1: 0; +} + + +/**************** + * Set bit N of A. + */ +void +mpi_set_bit( MPI a, unsigned n ) +{ + unsigned limbno, bitno; + + limbno = n / BITS_PER_MPI_LIMB; + bitno = n % BITS_PER_MPI_LIMB; + + if( limbno >= a->nlimbs ) { /* resize */ + if( a->alloced >= limbno ) + mpi_resize(a, limbno+1 ); + a->nlimbs = limbno+1; + } + a->d[limbno] |= (A_LIMB_1<= a->nlimbs ) { /* resize */ + if( a->alloced >= limbno ) + mpi_resize(a, limbno+1 ); + a->nlimbs = limbno+1; + } + a->d[limbno] |= (A_LIMB_1<d[limbno] &= ~(A_LIMB_1 << bitno); + a->nlimbs = limbno+1; +} + +/**************** + * clear bit N of A and all bits above + */ +void +mpi_clear_highbit( MPI a, unsigned n ) +{ + unsigned limbno, bitno; + + limbno = n / BITS_PER_MPI_LIMB; + bitno = n % BITS_PER_MPI_LIMB; + + if( limbno >= a->nlimbs ) + return; /* not allocated, so need to clear bits :-) */ + + for( ; bitno < BITS_PER_MPI_LIMB; bitno++ ) + a->d[limbno] &= ~(A_LIMB_1 << bitno); + a->nlimbs = limbno+1; +} + +/**************** + * Clear bit N of A. + */ +void +mpi_clear_bit( MPI a, unsigned n ) +{ + unsigned limbno, bitno; + + limbno = n / BITS_PER_MPI_LIMB; + bitno = n % BITS_PER_MPI_LIMB; + + if( limbno >= a->nlimbs ) + return; /* don't need to clear this bit, it's to far to left */ + a->d[limbno] &= ~(A_LIMB_1 << bitno); +} + + +/**************** + * Shift A by N bits to the right + * FIXME: should use alloc_limb if X and A are same. + */ +void +mpi_rshift( MPI x, MPI a, unsigned n ) +{ + mpi_ptr_t xp; + mpi_size_t xsize; + + xsize = a->nlimbs; + x->sign = a->sign; + RESIZE_IF_NEEDED(x, xsize); + xp = x->d; + + if( xsize ) { + mpihelp_rshift( xp, a->d, xsize, n); + MPN_NORMALIZE( xp, xsize); + } + x->nlimbs = xsize; +} + + +/**************** + * Shift A by COUNT limbs to the left + * This is used only within the MPI library + */ +void +mpi_lshift_limbs( MPI a, unsigned int count ) +{ + mpi_ptr_t ap = a->d; + int n = a->nlimbs; + int i; + + if( !count || !n ) + return; + + RESIZE_IF_NEEDED( a, n+count ); + + for( i = n-1; i >= 0; i-- ) + ap[i+count] = ap[i]; + for(i=0; i < count; i++ ) + ap[i] = 0; + a->nlimbs += count; +} + + +/**************** + * Shift A by COUNT limbs to the right + * This is used only within the MPI library + */ +void +mpi_rshift_limbs( MPI a, unsigned int count ) +{ + mpi_ptr_t ap = a->d; + mpi_size_t n = a->nlimbs; + unsigned int i; + + if( count >= n ) { + a->nlimbs = 0; + return; + } + + for( i = 0; i < n - count; i++ ) + ap[i] = ap[i+count]; + ap[i] = 0; + a->nlimbs -= count; +} + + diff -uNr a/eucrypt/mpi/mpi-cmp.c b/eucrypt/mpi/mpi-cmp.c --- a/eucrypt/mpi/mpi-cmp.c false +++ b/eucrypt/mpi/mpi-cmp.c 9225d6faa31311ea2857e6c9a8ad497846f41eca0bf07b0ebc7601b05251af751e68226ce7bb6b9f261fb182a5be9bb1a05aee4f222764d2f9ca28bfc59cfa99 @@ -0,0 +1,77 @@ +/* mpi-cmp.c - MPI functions + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" + +int +mpi_cmp_ui( MPI u, unsigned long v ) +{ + mpi_limb_t limb = v; + + mpi_normalize( u ); + if( !u->nlimbs && !limb ) + return 0; + if( u->sign ) + return -1; + if( u->nlimbs > 1 ) + return 1; + + if( u->d[0] == limb ) + return 0; + else if( u->d[0] > limb ) + return 1; + else + return -1; +} + +int +mpi_cmp( MPI u, MPI v ) +{ + mpi_size_t usize, vsize; + int cmp; + + mpi_normalize( u ); + mpi_normalize( v ); + usize = u->nlimbs; + vsize = v->nlimbs; + if( !u->sign && v->sign ) + return 1; + if( u->sign && !v->sign ) + return -1; + if( usize != vsize && !u->sign && !v->sign ) + return usize - vsize; + if( usize != vsize && u->sign && v->sign ) + return vsize + usize; + if( !usize ) + return 0; + if( !(cmp=mpihelp_cmp( u->d, v->d, usize )) ) + return 0; + if( (cmp < 0?1:0) == (u->sign?1:0)) + return 1; + return -1; +} + + diff -uNr a/eucrypt/mpi/mpi-div.c b/eucrypt/mpi/mpi-div.c --- a/eucrypt/mpi/mpi-div.c false +++ b/eucrypt/mpi/mpi-div.c 4c816e02a36adbcae224e0f6ecbef7d46811a2add9d33b677165936bee0d5e8b4900490904c25e0eae3e8616cc3bd7f7df13269ea4adde641814be563f820667 @@ -0,0 +1,316 @@ +/* mpi-div.c - MPI functions + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" +#include "longlong.h" + + + +void +mpi_fdiv_r( MPI rem, MPI dividend, MPI divisor ) +{ + int divisor_sign = divisor->sign; + MPI temp_divisor = NULL; + + /* We need the original value of the divisor after the remainder has been + * preliminary calculated. We have to copy it to temporary space if it's + * the same variable as REM. */ + if( rem == divisor ) { + temp_divisor = mpi_copy( divisor ); + divisor = temp_divisor; + } + + mpi_tdiv_r( rem, dividend, divisor ); + + if( ((divisor_sign?1:0) ^ (dividend->sign?1:0)) && rem->nlimbs ) + mpi_add( rem, rem, divisor); + + if( temp_divisor ) + mpi_free(temp_divisor); +} + + + +/**************** + * Division rounding the quotient towards -infinity. + * The remainder gets the same sign as the denominator. + * rem is optional + */ + +ulong +mpi_fdiv_r_ui( MPI rem, MPI dividend, ulong divisor ) +{ + mpi_limb_t rlimb; + + rlimb = mpihelp_mod_1( dividend->d, dividend->nlimbs, divisor ); + if( rlimb && dividend->sign ) + rlimb = divisor - rlimb; + + if( rem ) { + rem->d[0] = rlimb; + rem->nlimbs = rlimb? 1:0; + } + return rlimb; +} + + +void +mpi_fdiv_q( MPI quot, MPI dividend, MPI divisor ) +{ + MPI tmp = mpi_alloc( mpi_get_nlimbs(quot) ); + mpi_fdiv_qr( quot, tmp, dividend, divisor); + mpi_free(tmp); +} + +void +mpi_fdiv_qr( MPI quot, MPI rem, MPI dividend, MPI divisor ) +{ + int divisor_sign = divisor->sign; + MPI temp_divisor = NULL; + + if( quot == divisor || rem == divisor ) { + temp_divisor = mpi_copy( divisor ); + divisor = temp_divisor; + } + + mpi_tdiv_qr( quot, rem, dividend, divisor ); + + if( (divisor_sign ^ dividend->sign) && rem->nlimbs ) { + mpi_sub_ui( quot, quot, 1 ); + mpi_add( rem, rem, divisor); + } + + if( temp_divisor ) + mpi_free(temp_divisor); +} + + +/* If den == quot, den needs temporary storage. + * If den == rem, den needs temporary storage. + * If num == quot, num needs temporary storage. + * If den has temporary storage, it can be normalized while being copied, + * i.e no extra storage should be allocated. + */ + +void +mpi_tdiv_r( MPI rem, MPI num, MPI den) +{ + mpi_tdiv_qr(NULL, rem, num, den ); +} + +void +mpi_tdiv_qr( MPI quot, MPI rem, MPI num, MPI den) +{ + mpi_ptr_t np, dp; + mpi_ptr_t qp, rp; + mpi_size_t nsize = num->nlimbs; + mpi_size_t dsize = den->nlimbs; + mpi_size_t qsize, rsize; + mpi_size_t sign_remainder = num->sign; + mpi_size_t sign_quotient = num->sign ^ den->sign; + unsigned normalization_steps; + mpi_limb_t q_limb; + mpi_ptr_t marker[5]; + int markidx=0; + + /* Ensure space is enough for quotient and remainder. + * We need space for an extra limb in the remainder, because it's + * up-shifted (normalized) below. */ + rsize = nsize + 1; + mpi_resize( rem, rsize); + + qsize = rsize - dsize; /* qsize cannot be bigger than this. */ + if( qsize <= 0 ) { + if( num != rem ) { + rem->nlimbs = num->nlimbs; + rem->sign = num->sign; + MPN_COPY(rem->d, num->d, nsize); + } + if( quot ) { + /* This needs to follow the assignment to rem, in case the + * numerator and quotient are the same. */ + quot->nlimbs = 0; + quot->sign = 0; + } + return; + } + + if( quot ) + mpi_resize( quot, qsize); + + /* Read pointers here, when reallocation is finished. */ + np = num->d; + dp = den->d; + rp = rem->d; + + /* Optimize division by a single-limb divisor. */ + if( dsize == 1 ) { + mpi_limb_t rlimb; + if( quot ) { + qp = quot->d; + rlimb = mpihelp_divmod_1( qp, np, nsize, dp[0] ); + qsize -= qp[qsize - 1] == 0; + quot->nlimbs = qsize; + quot->sign = sign_quotient; + } + else + rlimb = mpihelp_mod_1( np, nsize, dp[0] ); + rp[0] = rlimb; + rsize = rlimb != 0?1:0; + rem->nlimbs = rsize; + rem->sign = sign_remainder; + return; + } + + + if( quot ) { + qp = quot->d; + /* Make sure QP and NP point to different objects. Otherwise the + * numerator would be gradually overwritten by the quotient limbs. */ + if(qp == np) { /* Copy NP object to temporary space. */ + np = marker[markidx++] = mpi_alloc_limb_space(nsize, + mpi_is_secure(quot)); + MPN_COPY(np, qp, nsize); + } + } + else /* Put quotient at top of remainder. */ + qp = rp + dsize; + + count_leading_zeros( normalization_steps, dp[dsize - 1] ); + + /* Normalize the denominator, i.e. make its most significant bit set by + * shifting it NORMALIZATION_STEPS bits to the left. Also shift the + * numerator the same number of steps (to keep the quotient the same!). + */ + if( normalization_steps ) { + mpi_ptr_t tp; + mpi_limb_t nlimb; + + /* Shift up the denominator setting the most significant bit of + * the most significant word. Use temporary storage not to clobber + * the original contents of the denominator. */ + tp = marker[markidx++] = mpi_alloc_limb_space(dsize,mpi_is_secure(den)); + mpihelp_lshift( tp, dp, dsize, normalization_steps ); + dp = tp; + + /* Shift up the numerator, possibly introducing a new most + * significant word. Move the shifted numerator in the remainder + * meanwhile. */ + nlimb = mpihelp_lshift(rp, np, nsize, normalization_steps); + if( nlimb ) { + rp[nsize] = nlimb; + rsize = nsize + 1; + } + else + rsize = nsize; + } + else { + /* The denominator is already normalized, as required. Copy it to + * temporary space if it overlaps with the quotient or remainder. */ + if( dp == rp || (quot && (dp == qp))) { + mpi_ptr_t tp; + + tp = marker[markidx++] = mpi_alloc_limb_space(dsize, mpi_is_secure(den)); + MPN_COPY( tp, dp, dsize ); + dp = tp; + } + + /* Move the numerator to the remainder. */ + if( rp != np ) + MPN_COPY(rp, np, nsize); + + rsize = nsize; + } + + q_limb = mpihelp_divrem( qp, 0, rp, rsize, dp, dsize ); + + if( quot ) { + qsize = rsize - dsize; + if(q_limb) { + qp[qsize] = q_limb; + qsize += 1; + } + + quot->nlimbs = qsize; + quot->sign = sign_quotient; + } + + rsize = dsize; + MPN_NORMALIZE (rp, rsize); + + if( normalization_steps && rsize ) { + mpihelp_rshift(rp, rp, rsize, normalization_steps); + rsize -= rp[rsize - 1] == 0?1:0; + } + + rem->nlimbs = rsize; + rem->sign = sign_remainder; + while( markidx ) + mpi_free_limb_space(marker[--markidx]); +} + +void +mpi_tdiv_q_2exp( MPI w, MPI u, unsigned count ) +{ + mpi_size_t usize, wsize; + mpi_size_t limb_cnt; + + usize = u->nlimbs; + limb_cnt = count / BITS_PER_MPI_LIMB; + wsize = usize - limb_cnt; + if( limb_cnt >= usize ) + w->nlimbs = 0; + else { + mpi_ptr_t wp; + mpi_ptr_t up; + + RESIZE_IF_NEEDED( w, wsize ); + wp = w->d; + up = u->d; + + count %= BITS_PER_MPI_LIMB; + if( count ) { + mpihelp_rshift( wp, up + limb_cnt, wsize, count ); + wsize -= !wp[wsize - 1]; + } + else { + MPN_COPY_INCR( wp, up + limb_cnt, wsize); + } + + w->nlimbs = wsize; + } +} + +/**************** + * Check whether dividend is divisible by divisor + * (note: divisor must fit into a limb) + */ +int +mpi_divisible_ui(MPI dividend, ulong divisor ) +{ + return !mpihelp_mod_1( dividend->d, dividend->nlimbs, divisor ); +} + diff -uNr a/eucrypt/mpi/mpi-gcd.c b/eucrypt/mpi/mpi-gcd.c --- a/eucrypt/mpi/mpi-gcd.c false +++ b/eucrypt/mpi/mpi-gcd.c 0ad3099f1db858eb1d25e7bccc7461f981adab9f7853346ef97a161639d3bcc31f22539abb342c96eb087f0fce3c91bb26a7e9c78c92dc33ca1fca5efcf534fe @@ -0,0 +1,57 @@ +/* mpi-gcd.c - MPI functions + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" + +/**************** + * Find the greatest common divisor G of A and B. + * Return: true if this 1, false in all other cases + */ +int +mpi_gcd( MPI g, MPI xa, MPI xb ) +{ + MPI a, b; + + a = mpi_copy(xa); + b = mpi_copy(xb); + + /* TAOCP Vol II, 4.5.2, Algorithm A */ + a->sign = 0; + b->sign = 0; + while( mpi_cmp_ui( b, 0 ) ) { + mpi_fdiv_r( g, a, b ); /* g used as temorary variable */ + mpi_set(a,b); + mpi_set(b,g); + } + mpi_set(g, a); + + mpi_free(a); + mpi_free(b); + return !mpi_cmp_ui( g, 1); +} + + + diff -uNr a/eucrypt/mpi/mpi-inline.c b/eucrypt/mpi/mpi-inline.c --- a/eucrypt/mpi/mpi-inline.c false +++ b/eucrypt/mpi/mpi-inline.c f9c2a485a76a2a0c12704d4683a4dc6a891b82217eb70b6fee22d4cde87fe7453c99463136a677c4520f9ace2b110ebd856214afdec5104eb2cb0774573f09ca @@ -0,0 +1,39 @@ +/* mpi-inline.c + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include + +#include "knobs.h" + +/* put the inline functions as real functions into the lib */ +#define G10_MPI_INLINE_DECL + +#include "mpi-internal.h" + +/* always include the header becuase it is only + * included by mpi-internal if __GCC__ is defined but we + * need it here in all cases and the above definition of + * of the macro allows us to do so + */ +#include "mpi-inline.h" + diff -uNr a/eucrypt/mpi/mpi-inv.c b/eucrypt/mpi/mpi-inv.c --- a/eucrypt/mpi/mpi-inv.c false +++ b/eucrypt/mpi/mpi-inv.c bd7b8bd954f2ddd627a55179b48c589dee37155ba3a2984c0e7ad6cc32c1c4a53dd0e9be5bd9a1ec1b6ee9c04e98dd40adfb2fec78bd2f24ff4e6ec6f723cb55 @@ -0,0 +1,270 @@ +/* mpi-inv.c - MPI functions + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" + + +/**************** + * Calculate the multiplicative inverse X of A mod N + * That is: Find the solution x for + * 1 = (a*x) mod n + */ +void +mpi_invm( MPI x, MPI a, MPI n ) +{ +#if 0 + MPI u, v, u1, u2, u3, v1, v2, v3, q, t1, t2, t3; + MPI ta, tb, tc; + + u = mpi_copy(a); + v = mpi_copy(n); + u1 = mpi_alloc_set_ui(1); + u2 = mpi_alloc_set_ui(0); + u3 = mpi_copy(u); + v1 = mpi_alloc_set_ui(0); + v2 = mpi_alloc_set_ui(1); + v3 = mpi_copy(v); + q = mpi_alloc( mpi_get_nlimbs(u)+1 ); + t1 = mpi_alloc( mpi_get_nlimbs(u)+1 ); + t2 = mpi_alloc( mpi_get_nlimbs(u)+1 ); + t3 = mpi_alloc( mpi_get_nlimbs(u)+1 ); + while( mpi_cmp_ui( v3, 0 ) ) { + mpi_fdiv_q( q, u3, v3 ); + mpi_mul(t1, v1, q); mpi_mul(t2, v2, q); mpi_mul(t3, v3, q); + mpi_sub(t1, u1, t1); mpi_sub(t2, u2, t2); mpi_sub(t3, u3, t3); + mpi_set(u1, v1); mpi_set(u2, v2); mpi_set(u3, v3); + mpi_set(v1, t1); mpi_set(v2, t2); mpi_set(v3, t3); + } + /* log_debug("result:\n"); + log_mpidump("q =", q ); + log_mpidump("u1=", u1); + log_mpidump("u2=", u2); + log_mpidump("u3=", u3); + log_mpidump("v1=", v1); + log_mpidump("v2=", v2); */ + mpi_set(x, u1); + + mpi_free(u1); + mpi_free(u2); + mpi_free(u3); + mpi_free(v1); + mpi_free(v2); + mpi_free(v3); + mpi_free(q); + mpi_free(t1); + mpi_free(t2); + mpi_free(t3); + mpi_free(u); + mpi_free(v); +#elif 0 + /* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X) + * modified according to Michael Penk's solution for Exercice 35 */ + + /* FIXME: we can simplify this in most cases (see Knuth) */ + MPI u, v, u1, u2, u3, v1, v2, v3, t1, t2, t3; + unsigned k; + int sign; + + u = mpi_copy(a); + v = mpi_copy(n); + for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) { + mpi_rshift(u, u, 1); + mpi_rshift(v, v, 1); + } + + + u1 = mpi_alloc_set_ui(1); + u2 = mpi_alloc_set_ui(0); + u3 = mpi_copy(u); + v1 = mpi_copy(v); /* !-- used as const 1 */ + v2 = mpi_alloc( mpi_get_nlimbs(u) ); mpi_sub( v2, u1, u ); + v3 = mpi_copy(v); + if( mpi_test_bit(u, 0) ) { /* u is odd */ + t1 = mpi_alloc_set_ui(0); + t2 = mpi_alloc_set_ui(1); t2->sign = 1; + t3 = mpi_copy(v); t3->sign = !t3->sign; + goto Y4; + } + else { + t1 = mpi_alloc_set_ui(1); + t2 = mpi_alloc_set_ui(0); + t3 = mpi_copy(u); + } + do { + do { + if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) { /* one is odd */ + mpi_add(t1, t1, v); + mpi_sub(t2, t2, u); + } + mpi_rshift(t1, t1, 1); + mpi_rshift(t2, t2, 1); + mpi_rshift(t3, t3, 1); + Y4: + ; + } while( !mpi_test_bit( t3, 0 ) ); /* while t3 is even */ + + if( !t3->sign ) { + mpi_set(u1, t1); + mpi_set(u2, t2); + mpi_set(u3, t3); + } + else { + mpi_sub(v1, v, t1); + sign = u->sign; u->sign = !u->sign; + mpi_sub(v2, u, t2); + u->sign = sign; + sign = t3->sign; t3->sign = !t3->sign; + mpi_set(v3, t3); + t3->sign = sign; + } + mpi_sub(t1, u1, v1); + mpi_sub(t2, u2, v2); + mpi_sub(t3, u3, v3); + if( t1->sign ) { + mpi_add(t1, t1, v); + mpi_sub(t2, t2, u); + } + } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */ + /* mpi_lshift( u3, k ); */ + mpi_set(x, u1); + + mpi_free(u1); + mpi_free(u2); + mpi_free(u3); + mpi_free(v1); + mpi_free(v2); + mpi_free(v3); + mpi_free(t1); + mpi_free(t2); + mpi_free(t3); +#else + /* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X) + * modified according to Michael Penk's solution for Exercice 35 + * with further enhancement */ + MPI u, v, u1, u2=NULL, u3, v1, v2=NULL, v3, t1, t2=NULL, t3; + unsigned k; + int sign; + int odd ; + + u = mpi_copy(a); + v = mpi_copy(n); + + for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) { + mpi_rshift(u, u, 1); + mpi_rshift(v, v, 1); + } + odd = mpi_test_bit(v,0); + + u1 = mpi_alloc_set_ui(1); + if( !odd ) + u2 = mpi_alloc_set_ui(0); + u3 = mpi_copy(u); + v1 = mpi_copy(v); + if( !odd ) { + v2 = mpi_alloc( mpi_get_nlimbs(u) ); + mpi_sub( v2, u1, u ); /* U is used as const 1 */ + } + v3 = mpi_copy(v); + if( mpi_test_bit(u, 0) ) { /* u is odd */ + t1 = mpi_alloc_set_ui(0); + if( !odd ) { + t2 = mpi_alloc_set_ui(1); t2->sign = 1; + } + t3 = mpi_copy(v); t3->sign = !t3->sign; + goto Y4; + } + else { + t1 = mpi_alloc_set_ui(1); + if( !odd ) + t2 = mpi_alloc_set_ui(0); + t3 = mpi_copy(u); + } + do { + do { + if( !odd ) { + if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) { /* one is odd */ + mpi_add(t1, t1, v); + mpi_sub(t2, t2, u); + } + mpi_rshift(t1, t1, 1); + mpi_rshift(t2, t2, 1); + mpi_rshift(t3, t3, 1); + } + else { + if( mpi_test_bit(t1, 0) ) + mpi_add(t1, t1, v); + mpi_rshift(t1, t1, 1); + mpi_rshift(t3, t3, 1); + } + Y4: + ; + } while( !mpi_test_bit( t3, 0 ) ); /* while t3 is even */ + + if( !t3->sign ) { + mpi_set(u1, t1); + if( !odd ) + mpi_set(u2, t2); + mpi_set(u3, t3); + } + else { + mpi_sub(v1, v, t1); + sign = u->sign; u->sign = !u->sign; + if( !odd ) + mpi_sub(v2, u, t2); + u->sign = sign; + sign = t3->sign; t3->sign = !t3->sign; + mpi_set(v3, t3); + t3->sign = sign; + } + mpi_sub(t1, u1, v1); + if( !odd ) + mpi_sub(t2, u2, v2); + mpi_sub(t3, u3, v3); + if( t1->sign ) { + mpi_add(t1, t1, v); + if( !odd ) + mpi_sub(t2, t2, u); + } + } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */ + /* mpi_lshift( u3, k ); */ + mpi_set(x, u1); + + mpi_free(u1); + mpi_free(v1); + mpi_free(t1); + if( !odd ) { + mpi_free(u2); + mpi_free(v2); + mpi_free(t2); + } + mpi_free(u3); + mpi_free(v3); + mpi_free(t3); + + mpi_free(u); + mpi_free(v); +#endif +} diff -uNr a/eucrypt/mpi/mpi-mpow.c b/eucrypt/mpi/mpi-mpow.c --- a/eucrypt/mpi/mpi-mpow.c false +++ b/eucrypt/mpi/mpi-mpow.c 221190b0f2bade0e8f32e7abb9a0cda81a2b15a0abe6ab54596b4823c41149ebb93338fa4ce7c6c4809618a53a173003f7febd510f188509e0d7fdd466596130 @@ -0,0 +1,103 @@ +/* mpi-mpow.c - MPI functions + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" +#include "longlong.h" + + +static int +build_index( MPI *exparray, int k, int i, int t ) +{ + int j, bitno; + int idx = 0; + + bitno = t-i; + for(j=k-1; j >= 0; j-- ) { + idx <<= 1; + if( mpi_test_bit( exparray[j], bitno ) ) + idx |= 1; + } + return idx; +} + +/**************** + * RES = (BASE[0] ^ EXP[0]) * (BASE[1] ^ EXP[1]) * ... * mod M + */ +void +mpi_mulpowm( MPI res, MPI *basearray, MPI *exparray, MPI m) +{ + int k; /* number of elements */ + int t; /* bit size of largest exponent */ + int i, j, idx; + MPI *G; /* table with precomputed values of size 2^k */ + MPI tmp; + + for(k=0; basearray[k]; k++ ) + ; + assert(k); + for(t=0, i=0; (tmp=exparray[i]); i++ ) { + j = mpi_get_nbits(tmp); + if( j > t ) + t = j; + } + assert(i==k); + assert(t); + assert( k < 10 ); + + G = xmalloc_clear( (1<= 0 && idx < (1<. + */ + +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" + + +void +mpi_mul_ui( MPI prod, MPI mult, unsigned long small_mult ) +{ + mpi_size_t size, prod_size; + mpi_ptr_t prod_ptr; + mpi_limb_t cy; + int sign; + + size = mult->nlimbs; + sign = mult->sign; + + if( !size || !small_mult ) { + prod->nlimbs = 0; + prod->sign = 0; + return; + } + + prod_size = size + 1; + if( prod->alloced < prod_size ) + mpi_resize( prod, prod_size ); + prod_ptr = prod->d; + + cy = mpihelp_mul_1( prod_ptr, mult->d, size, (mpi_limb_t)small_mult ); + if( cy ) + prod_ptr[size++] = cy; + prod->nlimbs = size; + prod->sign = sign; +} + + +void +mpi_mul_2exp( MPI w, MPI u, unsigned long cnt) +{ + mpi_size_t usize, wsize, limb_cnt; + mpi_ptr_t wp; + mpi_limb_t wlimb; + int usign, wsign; + + usize = u->nlimbs; + usign = u->sign; + + if( !usize ) { + w->nlimbs = 0; + w->sign = 0; + return; + } + + limb_cnt = cnt / BITS_PER_MPI_LIMB; + wsize = usize + limb_cnt + 1; + if( w->alloced < wsize ) + mpi_resize(w, wsize ); + wp = w->d; + wsize = usize + limb_cnt; + wsign = usign; + + cnt %= BITS_PER_MPI_LIMB; + if( cnt ) { + wlimb = mpihelp_lshift( wp + limb_cnt, u->d, usize, cnt ); + if( wlimb ) { + wp[wsize] = wlimb; + wsize++; + } + } + else { + MPN_COPY_DECR( wp + limb_cnt, u->d, usize ); + } + + /* Zero all whole limbs at low end. Do it here and not before calling + * mpn_lshift, not to lose for U == W. */ + MPN_ZERO( wp, limb_cnt ); + + w->nlimbs = wsize; + w->sign = wsign; +} + + + +void +mpi_mul( MPI w, MPI u, MPI v) +{ + mpi_size_t usize, vsize, wsize; + mpi_ptr_t up, vp, wp; + mpi_limb_t cy; + int usign, vsign, usecure, vsecure, sign_product; + int assign_wp=0; + mpi_ptr_t tmp_limb=NULL; + + + if( u->nlimbs < v->nlimbs ) { /* Swap U and V. */ + usize = v->nlimbs; + usign = v->sign; + usecure = mpi_is_secure(v); + up = v->d; + vsize = u->nlimbs; + vsign = u->sign; + vsecure = mpi_is_secure(u); + vp = u->d; + } + else { + usize = u->nlimbs; + usign = u->sign; + usecure = mpi_is_secure(u); + up = u->d; + vsize = v->nlimbs; + vsign = v->sign; + vsecure = mpi_is_secure(v); + vp = v->d; + } + sign_product = usign ^ vsign; + wp = w->d; + + /* Ensure W has space enough to store the result. */ + wsize = usize + vsize; + if ( !mpi_is_secure (w) && (mpi_is_secure (u) || mpi_is_secure (v)) ) { + /* w is not allocated in secure space but u or v is. To make sure + * that no temporray results are stored in w, we temporary use + * a newly allocated limb space for w */ + wp = mpi_alloc_limb_space( wsize, 1 ); + assign_wp = 2; /* mark it as 2 so that we can later copy it back to + * mormal memory */ + } + else if( w->alloced < wsize ) { + if( wp == up || wp == vp ) { + wp = mpi_alloc_limb_space( wsize, mpi_is_secure(w) ); + assign_wp = 1; + } + else { + mpi_resize(w, wsize ); + wp = w->d; + } + } + else { /* Make U and V not overlap with W. */ + if( wp == up ) { + /* W and U are identical. Allocate temporary space for U. */ + up = tmp_limb = mpi_alloc_limb_space( usize, usecure ); + /* Is V identical too? Keep it identical with U. */ + if( wp == vp ) + vp = up; + /* Copy to the temporary space. */ + MPN_COPY( up, wp, usize ); + } + else if( wp == vp ) { + /* W and V are identical. Allocate temporary space for V. */ + vp = tmp_limb = mpi_alloc_limb_space( vsize, vsecure ); + /* Copy to the temporary space. */ + MPN_COPY( vp, wp, vsize ); + } + } + + if( !vsize ) + wsize = 0; + else { + cy = mpihelp_mul( wp, up, usize, vp, vsize ); + wsize -= cy? 0:1; + } + + if( assign_wp ) { + if (assign_wp == 2) { + /* copy the temp wp from secure memory back to normal memory */ + mpi_ptr_t tmp_wp = mpi_alloc_limb_space (wsize, 0); + MPN_COPY (tmp_wp, wp, wsize); + mpi_free_limb_space (wp); + wp = tmp_wp; + } + mpi_assign_limb_space( w, wp, wsize ); + } + w->nlimbs = wsize; + w->sign = sign_product; + if( tmp_limb ) + mpi_free_limb_space( tmp_limb ); +} + + +void +mpi_mulm( MPI w, MPI u, MPI v, MPI m) +{ + mpi_mul(w, u, v); + mpi_fdiv_r( w, w, m ); +} + diff -uNr a/eucrypt/mpi/mpi-pow.c b/eucrypt/mpi/mpi-pow.c --- a/eucrypt/mpi/mpi-pow.c false +++ b/eucrypt/mpi/mpi-pow.c bbb0c95d94298e81a2357fda16069a02ab02dc1b36a48e6585200df41e235c56ea25317c5a851aa7e9f5c5c5fbea684d039377205030715c3fd8e06f31d3ba6d @@ -0,0 +1,291 @@ +/* mpi-pow.c - MPI functions + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" +#include "longlong.h" + + + +/**************** + * RES = BASE ^ EXP mod MOD + */ +void +mpi_powm( MPI res, MPI base, MPI exponent, MPI mod) +{ + mpi_ptr_t rp, ep, mp, bp; + mpi_size_t esize, msize, bsize, rsize; + int esign, msign, bsign, rsign; + int esec, msec, bsec, rsec; + mpi_size_t size; + int mod_shift_cnt; + int negative_result; + mpi_ptr_t mp_marker=NULL, bp_marker=NULL, ep_marker=NULL; + mpi_ptr_t xp_marker=NULL; + int assign_rp=0; + mpi_ptr_t tspace = NULL; + mpi_size_t tsize=0; /* to avoid compiler warning */ + /* fixme: we should check that the warning is void*/ + + esize = exponent->nlimbs; + msize = mod->nlimbs; + size = 2 * msize; + esign = exponent->sign; + msign = mod->sign; + + esec = mpi_is_secure(exponent); + msec = mpi_is_secure(mod); + bsec = mpi_is_secure(base); + rsec = mpi_is_secure(res); + + rp = res->d; + ep = exponent->d; + + if( !msize ) + msize = 1 / msize; /* provoke a signal */ + + if( !esize ) { + /* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0 + * depending on if MOD equals 1. */ + rp[0] = 1; + res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1; + res->sign = 0; + goto leave; + } + + /* Normalize MOD (i.e. make its most significant bit set) as required by + * mpn_divrem. This will make the intermediate values in the calculation + * slightly larger, but the correct result is obtained after a final + * reduction using the original MOD value. */ + mp = mp_marker = mpi_alloc_limb_space(msize, msec); + count_leading_zeros( mod_shift_cnt, mod->d[msize-1] ); + if( mod_shift_cnt ) + mpihelp_lshift( mp, mod->d, msize, mod_shift_cnt ); + else + MPN_COPY( mp, mod->d, msize ); + + bsize = base->nlimbs; + bsign = base->sign; + if( bsize > msize ) { /* The base is larger than the module. Reduce it. */ + /* Allocate (BSIZE + 1) with space for remainder and quotient. + * (The quotient is (bsize - msize + 1) limbs.) */ + bp = bp_marker = mpi_alloc_limb_space( bsize + 1, bsec ); + MPN_COPY( bp, base->d, bsize ); + /* We don't care about the quotient, store it above the remainder, + * at BP + MSIZE. */ + mpihelp_divrem( bp + msize, 0, bp, bsize, mp, msize ); + bsize = msize; + /* Canonicalize the base, since we are going to multiply with it + * quite a few times. */ + MPN_NORMALIZE( bp, bsize ); + } + else + bp = base->d; + + if( !bsize ) { + res->nlimbs = 0; + res->sign = 0; + goto leave; + } + + if( res->alloced < size ) { + /* We have to allocate more space for RES. If any of the input + * parameters are identical to RES, defer deallocation of the old + * space. */ + if( rp == ep || rp == mp || rp == bp ) { + rp = mpi_alloc_limb_space( size, rsec ); + assign_rp = 1; + } + else { + mpi_resize( res, size ); + rp = res->d; + } + } + else { /* Make BASE, EXPONENT and MOD not overlap with RES. */ + if( rp == bp ) { + /* RES and BASE are identical. Allocate temp. space for BASE. */ + assert( !bp_marker ); + bp = bp_marker = mpi_alloc_limb_space( bsize, bsec ); + MPN_COPY(bp, rp, bsize); + } + if( rp == ep ) { + /* RES and EXPONENT are identical. + Allocate temp. space for EXPONENT. */ + ep = ep_marker = mpi_alloc_limb_space( esize, esec ); + MPN_COPY(ep, rp, esize); + } + if( rp == mp ) { + /* RES and MOD are identical. Allocate temporary space for MOD.*/ + assert( !mp_marker ); + mp = mp_marker = mpi_alloc_limb_space( msize, msec ); + MPN_COPY(mp, rp, msize); + } + } + + MPN_COPY( rp, bp, bsize ); + rsize = bsize; + rsign = bsign; + + { + mpi_size_t i; + mpi_ptr_t xp = xp_marker = mpi_alloc_limb_space( 2 * (msize + 1), msec ); + int c; + mpi_limb_t e; + mpi_limb_t carry_limb; + struct karatsuba_ctx karactx; + + memset( &karactx, 0, sizeof karactx ); + negative_result = (ep[0] & 1) && base->sign; + + i = esize - 1; + e = ep[i]; + count_leading_zeros (c, e); + e = (e << c) << 1; /* shift the exp bits to the left, lose msb */ + c = BITS_PER_MPI_LIMB - 1 - c; + + /* Main loop. + * + * Make the result be pointed to alternately by XP and RP. This + * helps us avoid block copying, which would otherwise be necessary + * with the overlap restrictions of mpihelp_divmod. With 50% probability + * the result after this loop will be in the area originally pointed + * by RP (==RES->d), and with 50% probability in the area originally + * pointed to by XP. + */ + + for(;;) { + while( c ) { + mpi_ptr_t tp; + mpi_size_t xsize; + + /*mpihelp_mul_n(xp, rp, rp, rsize);*/ + if( rsize < KARATSUBA_THRESHOLD ) + mpih_sqr_n_basecase( xp, rp, rsize ); + else { + if( !tspace ) { + tsize = 2 * rsize; + tspace = mpi_alloc_limb_space( tsize, 0 ); + } + else if( tsize < (2*rsize) ) { + mpi_free_limb_space( tspace ); + tsize = 2 * rsize; + tspace = mpi_alloc_limb_space( tsize, 0 ); + } + mpih_sqr_n( xp, rp, rsize, tspace ); + } + + xsize = 2 * rsize; + if( xsize > msize ) { + mpihelp_divrem(xp + msize, 0, xp, xsize, mp, msize); + xsize = msize; + } + + tp = rp; rp = xp; xp = tp; + rsize = xsize; + + if( (mpi_limb_signed_t)e < 0 ) { + /*mpihelp_mul( xp, rp, rsize, bp, bsize );*/ + if( bsize < KARATSUBA_THRESHOLD ) { + mpihelp_mul( xp, rp, rsize, bp, bsize ); + } + else { + mpihelp_mul_karatsuba_case( + xp, rp, rsize, bp, bsize, &karactx ); + } + + xsize = rsize + bsize; + if( xsize > msize ) { + mpihelp_divrem(xp + msize, 0, xp, xsize, mp, msize); + xsize = msize; + } + + tp = rp; rp = xp; xp = tp; + rsize = xsize; + } + e <<= 1; + c--; + } + + i--; + if( i < 0 ) + break; + e = ep[i]; + c = BITS_PER_MPI_LIMB; + } + + /* We shifted MOD, the modulo reduction argument, left MOD_SHIFT_CNT + * steps. Adjust the result by reducing it with the original MOD. + * + * Also make sure the result is put in RES->d (where it already + * might be, see above). + */ + if( mod_shift_cnt ) { + carry_limb = mpihelp_lshift( res->d, rp, rsize, mod_shift_cnt); + rp = res->d; + if( carry_limb ) { + rp[rsize] = carry_limb; + rsize++; + } + } + else { + MPN_COPY( res->d, rp, rsize); + rp = res->d; + } + + if( rsize >= msize ) { + mpihelp_divrem(rp + msize, 0, rp, rsize, mp, msize); + rsize = msize; + } + + /* Remove any leading zero words from the result. */ + if( mod_shift_cnt ) + mpihelp_rshift( rp, rp, rsize, mod_shift_cnt); + MPN_NORMALIZE (rp, rsize); + + mpihelp_release_karatsuba_ctx( &karactx ); + } + + if( negative_result && rsize ) { + if( mod_shift_cnt ) + mpihelp_rshift( mp, mp, msize, mod_shift_cnt); + mpihelp_sub( rp, mp, msize, rp, rsize); + rsize = msize; + rsign = msign; + MPN_NORMALIZE(rp, rsize); + } + res->nlimbs = rsize; + res->sign = rsign; + + leave: + if( assign_rp ) mpi_assign_limb_space( res, rp, size ); + if( mp_marker ) mpi_free_limb_space( mp_marker ); + if( bp_marker ) mpi_free_limb_space( bp_marker ); + if( ep_marker ) mpi_free_limb_space( ep_marker ); + if( xp_marker ) mpi_free_limb_space( xp_marker ); + if( tspace ) mpi_free_limb_space( tspace ); +} + diff -uNr a/eucrypt/mpi/mpi-scan.c b/eucrypt/mpi/mpi-scan.c --- a/eucrypt/mpi/mpi-scan.c false +++ b/eucrypt/mpi/mpi-scan.c eaf2827058a07c1502ea5da210ae7b7662b6b02ac4847d37467fb498ddb84d592cce814db4b15588da8c5349e4ffe4636d267fedf0eceb29e63bd8dcf0249be2 @@ -0,0 +1,56 @@ +/* mpi-scan.c - MPI functions + * Modified by No Such Labs. (C) 2015. See README. + * Modified by S.MG 2017 (removed code that is not used by eucrypt and at the same time so ugly it needs rewrite anyway) + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" +#include "longlong.h" + + +/**************** + * Count the number of zerobits at the low end of A + * This is used currently by eucrypt's primality tests. + */ +unsigned int +mpi_trailing_zeros( MPI a ) +{ + unsigned n, count = 0; + + for(n=0; n < a->nlimbs; n++ ) { + if( a->d[n] ) { + unsigned nn; + mpi_limb_t alimb = a->d[n]; + + count_trailing_zeros( nn, alimb ); + count += nn; + break; + } + count += BITS_PER_MPI_LIMB; + } + return count; + +} + + diff -uNr a/eucrypt/mpi/mpicoder.c b/eucrypt/mpi/mpicoder.c --- a/eucrypt/mpi/mpicoder.c false +++ b/eucrypt/mpi/mpicoder.c e415fde563a94473cfe9e85e8862cf30f6c8b820f383f6a964aef675e576648bc9f66f55ba7ef01e27969fe57d14293b96daac1525197be392abb5c9b1ad4040 @@ -0,0 +1,347 @@ +/* mpicoder.c - Coder for the external representation of MPIs + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include +#include +#include + +#include "knobs.h" +#include "mpi.h" +#include "mpi-internal.h" +#include "memory.h" +#include "util.h" + +#ifdef M_DEBUG +#undef mpi_read +#endif + +#define MAX_EXTERN_MPI_BITS 16384 + + +MPI +mpi_read_from_buffer(byte *buffer, unsigned int *ret_nread, int secure) +{ + int i, j; + unsigned nbits, nbytes, nlimbs, nread=0; + mpi_limb_t a; + MPI val = NULL; + + if( *ret_nread < 2 ) + goto leave; + nbits = buffer[0] << 8 | buffer[1]; + if( nbits > MAX_EXTERN_MPI_BITS ) { + log_info ("mpi too large (%u bits)\n", nbits); + goto leave; + } + buffer += 2; + nread = 2; + + nbytes = (nbits+7) / 8; + nlimbs = (nbytes+BYTES_PER_MPI_LIMB-1) / BYTES_PER_MPI_LIMB; + val = secure? mpi_alloc_secure( nlimbs ) + : mpi_alloc( nlimbs ); + i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB; + i %= BYTES_PER_MPI_LIMB; + val->nbits = nbits; + j= val->nlimbs = nlimbs; + val->sign = 0; + for( ; j > 0; j-- ) { + a = 0; + for(; i < BYTES_PER_MPI_LIMB; i++ ) { + if( ++nread > *ret_nread ) { + /* This (as well as the above error condition) may + happen if we use this function to parse a decrypted + MPI which didn't turn out to be a real MPI - possible + because the supplied key was wrong but the OpenPGP + checksum didn't caught it. */ + log_info ("mpi larger than buffer\n"); + mpi_free (val); + val = NULL; + goto leave; + } + a <<= 8; + a |= *buffer++; + } + i = 0; + val->d[j-1] = a; + } + + leave: + *ret_nread = nread; + return val; +} + + +/**************** + * Make an mpi from a character string. + */ +int +mpi_fromstr(MPI val, const char *str) +{ + int hexmode=0, sign=0, prepend_zero=0, i, j, c, c1, c2; + unsigned nbits, nbytes, nlimbs; + mpi_limb_t a; + + if( *str == '-' ) { + sign = 1; + str++; + } + if( *str == '0' && str[1] == 'x' ) + hexmode = 1; + else + return 1; /* other bases are not yet supported */ + str += 2; + + nbits = strlen(str)*4; + if( nbits % 8 ) + prepend_zero = 1; + nbytes = (nbits+7) / 8; + nlimbs = (nbytes+BYTES_PER_MPI_LIMB-1) / BYTES_PER_MPI_LIMB; + if( val->alloced < nlimbs ) + mpi_resize(val, nlimbs ); + i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB; + i %= BYTES_PER_MPI_LIMB; + j= val->nlimbs = nlimbs; + val->sign = sign; + for( ; j > 0; j-- ) { + a = 0; + for(; i < BYTES_PER_MPI_LIMB; i++ ) { + if( prepend_zero ) { + c1 = '0'; + prepend_zero = 0; + } + else + c1 = *str++; + assert(c1); + c2 = *str++; + assert(c2); + if( c1 >= '0' && c1 <= '9' ) + c = c1 - '0'; + else if( c1 >= 'a' && c1 <= 'f' ) + c = c1 - 'a' + 10; + else if( c1 >= 'A' && c1 <= 'F' ) + c = c1 - 'A' + 10; + else { + mpi_clear(val); + return 1; + } + c <<= 4; + if( c2 >= '0' && c2 <= '9' ) + c |= c2 - '0'; + else if( c2 >= 'a' && c2 <= 'f' ) + c |= c2 - 'a' + 10; + else if( c2 >= 'A' && c2 <= 'F' ) + c |= c2 - 'A' + 10; + else { + mpi_clear(val); + return 1; + } + a <<= 8; + a |= c; + } + i = 0; + val->d[j-1] = a; + } + + return 0; +} + + +/**************** + * print an MPI to the given stream and return the number of characters + * printed. + */ +int +mpi_print( FILE *fp, MPI a, int mode ) +{ + int i, n=0; + + if( a == NULL ) + return fprintf(fp, "[MPI_NULL]"); + if( !mode ) { + unsigned int n1; + + n1 = mpi_get_nbits(a); + n += fprintf(fp, "[%u bits]", n1); + } + else { + if( a->sign ) + putc('-', fp); +#if BYTES_PER_MPI_LIMB == 2 +#define X "4" +#elif BYTES_PER_MPI_LIMB == 4 +#define X "8" +#elif BYTES_PER_MPI_LIMB == 8 +#define X "16" +#else +#error please define the format here +#endif + for(i=a->nlimbs; i > 0 ; i-- ) { + n += fprintf(fp, i!=a->nlimbs? "%0" X "lX":"%lX", (ulong)a->d[i-1]); +#undef X + } + if( !a->nlimbs ) + putc('0', fp ); + } + return n; +} + + +/* +void +g10_log_mpidump( const char *text, MPI a ) +{ + FILE *fp = log_stream(); + + g10_log_print_prefix(text); + mpi_print(fp, a, 1 ); + fputc('\n', fp); +} +*/ + + +/**************** + * Return an xmalloced buffer with the MPI (msb first). + * NBYTES receives the length of this buffer. Caller must free the + * return string (This function does return a 0 byte buffer with NBYTES + * set to zero if the value of A is zero. If sign is not NULL, it will + * be set to the sign of the A. + */ +static byte * +do_get_buffer( MPI a, unsigned *nbytes, int *sign, int force_secure ) +{ + byte *p, *buffer; + mpi_limb_t alimb; + int i; + unsigned int n; + + if( sign ) + *sign = a->sign; + *nbytes = n = a->nlimbs * BYTES_PER_MPI_LIMB; + if (!n) + n++; /* avoid zero length allocation */ + p = buffer = force_secure || mpi_is_secure(a) ? xmalloc_secure(n) + : xmalloc(n); + + for(i=a->nlimbs-1; i >= 0; i-- ) { + alimb = a->d[i]; +#if BYTES_PER_MPI_LIMB == 4 + *p++ = alimb >> 24; + *p++ = alimb >> 16; + *p++ = alimb >> 8; + *p++ = alimb ; +#elif BYTES_PER_MPI_LIMB == 8 + *p++ = alimb >> 56; + *p++ = alimb >> 48; + *p++ = alimb >> 40; + *p++ = alimb >> 32; + *p++ = alimb >> 24; + *p++ = alimb >> 16; + *p++ = alimb >> 8; + *p++ = alimb ; +#else +#error please implement for this limb size. +#endif + } + + /* this is sub-optimal but we need to do the shift operation + * because the caller has to free the returned buffer */ + for(p=buffer; !*p && *nbytes; p++, --*nbytes ) + ; + if( p != buffer ) + memmove(buffer,p, *nbytes); + + return buffer; +} + + +byte * +mpi_get_buffer( MPI a, unsigned *nbytes, int *sign ) +{ + return do_get_buffer( a, nbytes, sign, 0 ); +} + +byte * +mpi_get_secure_buffer( MPI a, unsigned *nbytes, int *sign ) +{ + return do_get_buffer( a, nbytes, sign, 1 ); +} + +/**************** + * Use BUFFER to update MPI. + */ +void +mpi_set_buffer( MPI a, const byte *buffer, unsigned nbytes, int sign ) +{ + const byte *p; + mpi_limb_t alimb; + int nlimbs; + int i; + + nlimbs = (nbytes + BYTES_PER_MPI_LIMB - 1) / BYTES_PER_MPI_LIMB; + RESIZE_IF_NEEDED(a, nlimbs); + a->sign = sign; + + for(i=0, p = buffer+nbytes-1; p >= buffer+BYTES_PER_MPI_LIMB; ) { +#if BYTES_PER_MPI_LIMB == 4 + alimb = (mpi_limb_t)*p-- ; + alimb |= (mpi_limb_t)*p-- << 8 ; + alimb |= (mpi_limb_t)*p-- << 16 ; + alimb |= (mpi_limb_t)*p-- << 24 ; +#elif BYTES_PER_MPI_LIMB == 8 + alimb = (mpi_limb_t)*p-- ; + alimb |= (mpi_limb_t)*p-- << 8 ; + alimb |= (mpi_limb_t)*p-- << 16 ; + alimb |= (mpi_limb_t)*p-- << 24 ; + alimb |= (mpi_limb_t)*p-- << 32 ; + alimb |= (mpi_limb_t)*p-- << 40 ; + alimb |= (mpi_limb_t)*p-- << 48 ; + alimb |= (mpi_limb_t)*p-- << 56 ; +#else +#error please implement for this limb size. +#endif + a->d[i++] = alimb; + } + if( p >= buffer ) { +#if BYTES_PER_MPI_LIMB == 4 + alimb = *p-- ; + if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 8 ; + if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 16 ; + if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 24 ; +#elif BYTES_PER_MPI_LIMB == 8 + alimb = (mpi_limb_t)*p-- ; + if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 8 ; + if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 16 ; + if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 24 ; + if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 32 ; + if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 40 ; + if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 48 ; + if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 56 ; +#else +#error please implement for this limb size. +#endif + a->d[i++] = alimb; + } + a->nlimbs = i; + assert( i == nlimbs ); +} diff -uNr a/eucrypt/mpi/mpih-add1.c b/eucrypt/mpi/mpih-add1.c --- a/eucrypt/mpi/mpih-add1.c false +++ b/eucrypt/mpi/mpih-add1.c b5713900ed6f31370c3136b3bebc4a96603a0f319d1e75abd706219bd6fdd5c5105f9e33275df06abd1321552ffc342dcf41c15cc28873faee616a0d62974467 @@ -0,0 +1,59 @@ +/* mpihelp-add_1.c - MPI helper functions + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" +#include "longlong.h" + +mpi_limb_t +mpihelp_add_n( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_ptr_t s2_ptr, mpi_size_t size) +{ + mpi_limb_t x, y, cy; + mpi_size_t j; + + /* The loop counter and index J goes from -SIZE to -1. This way + the loop becomes faster. */ + j = -size; + + /* Offset the base pointers to compensate for the negative indices. */ + s1_ptr -= j; + s2_ptr -= j; + res_ptr -= j; + + cy = 0; + do { + y = s2_ptr[j]; + x = s1_ptr[j]; + y += cy; /* add previous carry to one addend */ + cy = y < cy; /* get out carry from that addition */ + y += x; /* add other addend */ + cy += y < x; /* get out carry from that add, combine */ + res_ptr[j] = y; + } while( ++j ); + + return cy; +} + diff -uNr a/eucrypt/mpi/mpih-cmp.c b/eucrypt/mpi/mpih-cmp.c --- a/eucrypt/mpi/mpih-cmp.c false +++ b/eucrypt/mpi/mpih-cmp.c e789cea1e3a670f80f48773ae523b6ba57fa5bdbc170d552037871c9e22f04bc697ed636c9dcc13bdaf1ddc7e86748cee33cf8519f619e8e6f7f4486a549c881 @@ -0,0 +1,55 @@ +/* mpihelp-sub.c - MPI helper functions + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" + +/**************** + * Compare OP1_PTR/OP1_SIZE with OP2_PTR/OP2_SIZE. + * There are no restrictions on the relative sizes of + * the two arguments. + * Return 1 if OP1 > OP2, 0 if they are equal, and -1 if OP1 < OP2. + */ +int +mpihelp_cmp( mpi_ptr_t op1_ptr, mpi_ptr_t op2_ptr, mpi_size_t size ) +{ + mpi_size_t i; + mpi_limb_t op1_word, op2_word; + + for( i = size - 1; i >= 0 ; i--) { + op1_word = op1_ptr[i]; + op2_word = op2_ptr[i]; + if( op1_word != op2_word ) + goto diff; + } + return 0; + + diff: + /* This can *not* be simplified to + * op2_word - op2_word + * since that expression might give signed overflow. */ + return (op1_word > op2_word) ? 1 : -1; +} + diff -uNr a/eucrypt/mpi/mpih-div.c b/eucrypt/mpi/mpih-div.c --- a/eucrypt/mpi/mpih-div.c false +++ b/eucrypt/mpi/mpih-div.c 49ef731356e9c2e54d04cb0f5c4a68285ad1ca1c27015aacefda5f0cb5ac676a0dc47b1656ab2057e1cffcc58e837b1010e85391a8f570ccdda24630b28620f7 @@ -0,0 +1,529 @@ +/* mpihelp-div.c - MPI helper functions + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" +#include "longlong.h" + +#ifndef UMUL_TIME +#define UMUL_TIME 1 +#endif +#ifndef UDIV_TIME +#define UDIV_TIME UMUL_TIME +#endif + +/* FIXME: We should be using invert_limb (or invert_normalized_limb) + * here (not udiv_qrnnd). + */ + +mpi_limb_t +mpihelp_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size, + mpi_limb_t divisor_limb) +{ + mpi_size_t i; + mpi_limb_t n1, n0, r; + int dummy; + + /* Botch: Should this be handled at all? Rely on callers? */ + if( !dividend_size ) + return 0; + + /* If multiplication is much faster than division, and the + * dividend is large, pre-invert the divisor, and use + * only multiplications in the inner loop. + * + * This test should be read: + * Does it ever help to use udiv_qrnnd_preinv? + * && Does what we save compensate for the inversion overhead? + */ + if( UDIV_TIME > (2 * UMUL_TIME + 6) + && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME ) { + int normalization_steps; + + count_leading_zeros( normalization_steps, divisor_limb ); + if( normalization_steps ) { + mpi_limb_t divisor_limb_inverted; + + divisor_limb <<= normalization_steps; + + /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The + * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the + * most significant bit (with weight 2**N) implicit. + * + * Special case for DIVISOR_LIMB == 100...000. + */ + if( !(divisor_limb << 1) ) + divisor_limb_inverted = ~(mpi_limb_t)0; + else + udiv_qrnnd(divisor_limb_inverted, dummy, + -divisor_limb, 0, divisor_limb); + + n1 = dividend_ptr[dividend_size - 1]; + r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps); + + /* Possible optimization: + * if (r == 0 + * && divisor_limb > ((n1 << normalization_steps) + * | (dividend_ptr[dividend_size - 2] >> ...))) + * ...one division less... + */ + for( i = dividend_size - 2; i >= 0; i--) { + n0 = dividend_ptr[i]; + UDIV_QRNND_PREINV(dummy, r, r, + ((n1 << normalization_steps) + | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))), + divisor_limb, divisor_limb_inverted); + n1 = n0; + } + UDIV_QRNND_PREINV(dummy, r, r, + n1 << normalization_steps, + divisor_limb, divisor_limb_inverted); + return r >> normalization_steps; + } + else { + mpi_limb_t divisor_limb_inverted; + + /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The + * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the + * most significant bit (with weight 2**N) implicit. + * + * Special case for DIVISOR_LIMB == 100...000. + */ + if( !(divisor_limb << 1) ) + divisor_limb_inverted = ~(mpi_limb_t)0; + else + udiv_qrnnd(divisor_limb_inverted, dummy, + -divisor_limb, 0, divisor_limb); + + i = dividend_size - 1; + r = dividend_ptr[i]; + + if( r >= divisor_limb ) + r = 0; + else + i--; + + for( ; i >= 0; i--) { + n0 = dividend_ptr[i]; + UDIV_QRNND_PREINV(dummy, r, r, + n0, divisor_limb, divisor_limb_inverted); + } + return r; + } + } + else { + if( UDIV_NEEDS_NORMALIZATION ) { + int normalization_steps; + + count_leading_zeros(normalization_steps, divisor_limb); + if( normalization_steps ) { + divisor_limb <<= normalization_steps; + + n1 = dividend_ptr[dividend_size - 1]; + r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps); + + /* Possible optimization: + * if (r == 0 + * && divisor_limb > ((n1 << normalization_steps) + * | (dividend_ptr[dividend_size - 2] >> ...))) + * ...one division less... + */ + for(i = dividend_size - 2; i >= 0; i--) { + n0 = dividend_ptr[i]; + udiv_qrnnd (dummy, r, r, + ((n1 << normalization_steps) + | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))), + divisor_limb); + n1 = n0; + } + udiv_qrnnd (dummy, r, r, + n1 << normalization_steps, + divisor_limb); + return r >> normalization_steps; + } + } + /* No normalization needed, either because udiv_qrnnd doesn't require + * it, or because DIVISOR_LIMB is already normalized. */ + i = dividend_size - 1; + r = dividend_ptr[i]; + + if(r >= divisor_limb) + r = 0; + else + i--; + + for(; i >= 0; i--) { + n0 = dividend_ptr[i]; + udiv_qrnnd (dummy, r, r, n0, divisor_limb); + } + return r; + } +} + +/* Divide num (NP/NSIZE) by den (DP/DSIZE) and write + * the NSIZE-DSIZE least significant quotient limbs at QP + * and the DSIZE long remainder at NP. If QEXTRA_LIMBS is + * non-zero, generate that many fraction bits and append them after the + * other quotient limbs. + * Return the most significant limb of the quotient, this is always 0 or 1. + * + * Preconditions: + * 0. NSIZE >= DSIZE. + * 1. The most significant bit of the divisor must be set. + * 2. QP must either not overlap with the input operands at all, or + * QP + DSIZE >= NP must hold true. (This means that it's + * possible to put the quotient in the high part of NUM, right after the + * remainder in NUM. + * 3. NSIZE >= DSIZE, even if QEXTRA_LIMBS is non-zero. + */ + +mpi_limb_t +mpihelp_divrem( mpi_ptr_t qp, mpi_size_t qextra_limbs, + mpi_ptr_t np, mpi_size_t nsize, + mpi_ptr_t dp, mpi_size_t dsize) +{ + mpi_limb_t most_significant_q_limb = 0; + + switch(dsize) { + case 0: + /* We are asked to divide by zero, so go ahead and do it! (To make + the compiler not remove this statement, return the value.) */ + return 1 / dsize; + + case 1: + { + mpi_size_t i; + mpi_limb_t n1; + mpi_limb_t d; + + d = dp[0]; + n1 = np[nsize - 1]; + + if( n1 >= d ) { + n1 -= d; + most_significant_q_limb = 1; + } + + qp += qextra_limbs; + for( i = nsize - 2; i >= 0; i--) + udiv_qrnnd( qp[i], n1, n1, np[i], d ); + qp -= qextra_limbs; + + for( i = qextra_limbs - 1; i >= 0; i-- ) + udiv_qrnnd (qp[i], n1, n1, 0, d); + + np[0] = n1; + } + break; + + case 2: + { + mpi_size_t i; + mpi_limb_t n1, n0, n2; + mpi_limb_t d1, d0; + + np += nsize - 2; + d1 = dp[1]; + d0 = dp[0]; + n1 = np[1]; + n0 = np[0]; + + if( n1 >= d1 && (n1 > d1 || n0 >= d0) ) { + sub_ddmmss (n1, n0, n1, n0, d1, d0); + most_significant_q_limb = 1; + } + + for( i = qextra_limbs + nsize - 2 - 1; i >= 0; i-- ) { + mpi_limb_t q; + mpi_limb_t r; + + if( i >= qextra_limbs ) + np--; + else + np[0] = 0; + + if( n1 == d1 ) { + /* Q should be either 111..111 or 111..110. Need special + * treatment of this rare case as normal division would + * give overflow. */ + q = ~(mpi_limb_t)0; + + r = n0 + d1; + if( r < d1 ) { /* Carry in the addition? */ + add_ssaaaa( n1, n0, r - d0, np[0], 0, d0 ); + qp[i] = q; + continue; + } + n1 = d0 - (d0 != 0?1:0); + n0 = -d0; + } + else { + udiv_qrnnd (q, r, n1, n0, d1); + umul_ppmm (n1, n0, d0, q); + } + + n2 = np[0]; + q_test: + if( n1 > r || (n1 == r && n0 > n2) ) { + /* The estimated Q was too large. */ + q--; + sub_ddmmss (n1, n0, n1, n0, 0, d0); + r += d1; + if( r >= d1 ) /* If not carry, test Q again. */ + goto q_test; + } + + qp[i] = q; + sub_ddmmss (n1, n0, r, n2, n1, n0); + } + np[1] = n1; + np[0] = n0; + } + break; + + default: + { + mpi_size_t i; + mpi_limb_t dX, d1, n0; + + np += nsize - dsize; + dX = dp[dsize - 1]; + d1 = dp[dsize - 2]; + n0 = np[dsize - 1]; + + if( n0 >= dX ) { + if(n0 > dX || mpihelp_cmp(np, dp, dsize - 1) >= 0 ) { + mpihelp_sub_n(np, np, dp, dsize); + n0 = np[dsize - 1]; + most_significant_q_limb = 1; + } + } + + for( i = qextra_limbs + nsize - dsize - 1; i >= 0; i--) { + mpi_limb_t q; + mpi_limb_t n1, n2; + mpi_limb_t cy_limb; + + if( i >= qextra_limbs ) { + np--; + n2 = np[dsize]; + } + else { + n2 = np[dsize - 1]; + MPN_COPY_DECR (np + 1, np, dsize - 1); + np[0] = 0; + } + + if( n0 == dX ) { + /* This might over-estimate q, but it's probably not worth + * the extra code here to find out. */ + q = ~(mpi_limb_t)0; + } + else { + mpi_limb_t r; + + udiv_qrnnd(q, r, n0, np[dsize - 1], dX); + umul_ppmm(n1, n0, d1, q); + + while( n1 > r || (n1 == r && n0 > np[dsize - 2])) { + q--; + r += dX; + if( r < dX ) /* I.e. "carry in previous addition?" */ + break; + n1 -= n0 < d1; + n0 -= d1; + } + } + + /* Possible optimization: We already have (q * n0) and (1 * n1) + * after the calculation of q. Taking advantage of that, we + * could make this loop make two iterations less. */ + cy_limb = mpihelp_submul_1(np, dp, dsize, q); + + if( n2 != cy_limb ) { + mpihelp_add_n(np, np, dp, dsize); + q--; + } + + qp[i] = q; + n0 = np[dsize - 1]; + } + } + } + + return most_significant_q_limb; +} + + +/**************** + * Divide (DIVIDEND_PTR,,DIVIDEND_SIZE) by DIVISOR_LIMB. + * Write DIVIDEND_SIZE limbs of quotient at QUOT_PTR. + * Return the single-limb remainder. + * There are no constraints on the value of the divisor. + * + * QUOT_PTR and DIVIDEND_PTR might point to the same limb. + */ + +mpi_limb_t +mpihelp_divmod_1( mpi_ptr_t quot_ptr, + mpi_ptr_t dividend_ptr, mpi_size_t dividend_size, + mpi_limb_t divisor_limb) +{ + mpi_size_t i; + mpi_limb_t n1, n0, r; + int dummy; + + if( !dividend_size ) + return 0; + + /* If multiplication is much faster than division, and the + * dividend is large, pre-invert the divisor, and use + * only multiplications in the inner loop. + * + * This test should be read: + * Does it ever help to use udiv_qrnnd_preinv? + * && Does what we save compensate for the inversion overhead? + */ + if( UDIV_TIME > (2 * UMUL_TIME + 6) + && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME ) { + int normalization_steps; + + count_leading_zeros( normalization_steps, divisor_limb ); + if( normalization_steps ) { + mpi_limb_t divisor_limb_inverted; + + divisor_limb <<= normalization_steps; + + /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The + * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the + * most significant bit (with weight 2**N) implicit. + */ + /* Special case for DIVISOR_LIMB == 100...000. */ + if( !(divisor_limb << 1) ) + divisor_limb_inverted = ~(mpi_limb_t)0; + else + udiv_qrnnd(divisor_limb_inverted, dummy, + -divisor_limb, 0, divisor_limb); + + n1 = dividend_ptr[dividend_size - 1]; + r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps); + + /* Possible optimization: + * if (r == 0 + * && divisor_limb > ((n1 << normalization_steps) + * | (dividend_ptr[dividend_size - 2] >> ...))) + * ...one division less... + */ + for( i = dividend_size - 2; i >= 0; i--) { + n0 = dividend_ptr[i]; + UDIV_QRNND_PREINV( quot_ptr[i + 1], r, r, + ((n1 << normalization_steps) + | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))), + divisor_limb, divisor_limb_inverted); + n1 = n0; + } + UDIV_QRNND_PREINV( quot_ptr[0], r, r, + n1 << normalization_steps, + divisor_limb, divisor_limb_inverted); + return r >> normalization_steps; + } + else { + mpi_limb_t divisor_limb_inverted; + + /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The + * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the + * most significant bit (with weight 2**N) implicit. + */ + /* Special case for DIVISOR_LIMB == 100...000. */ + if( !(divisor_limb << 1) ) + divisor_limb_inverted = ~(mpi_limb_t) 0; + else + udiv_qrnnd(divisor_limb_inverted, dummy, + -divisor_limb, 0, divisor_limb); + + i = dividend_size - 1; + r = dividend_ptr[i]; + + if( r >= divisor_limb ) + r = 0; + else + quot_ptr[i--] = 0; + + for( ; i >= 0; i-- ) { + n0 = dividend_ptr[i]; + UDIV_QRNND_PREINV( quot_ptr[i], r, r, + n0, divisor_limb, divisor_limb_inverted); + } + return r; + } + } + else { + if(UDIV_NEEDS_NORMALIZATION) { + int normalization_steps; + + count_leading_zeros (normalization_steps, divisor_limb); + if( normalization_steps ) { + divisor_limb <<= normalization_steps; + + n1 = dividend_ptr[dividend_size - 1]; + r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps); + + /* Possible optimization: + * if (r == 0 + * && divisor_limb > ((n1 << normalization_steps) + * | (dividend_ptr[dividend_size - 2] >> ...))) + * ...one division less... + */ + for( i = dividend_size - 2; i >= 0; i--) { + n0 = dividend_ptr[i]; + udiv_qrnnd (quot_ptr[i + 1], r, r, + ((n1 << normalization_steps) + | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))), + divisor_limb); + n1 = n0; + } + udiv_qrnnd (quot_ptr[0], r, r, + n1 << normalization_steps, + divisor_limb); + return r >> normalization_steps; + } + } + /* No normalization needed, either because udiv_qrnnd doesn't require + * it, or because DIVISOR_LIMB is already normalized. */ + i = dividend_size - 1; + r = dividend_ptr[i]; + + if(r >= divisor_limb) + r = 0; + else + quot_ptr[i--] = 0; + + for(; i >= 0; i--) { + n0 = dividend_ptr[i]; + udiv_qrnnd( quot_ptr[i], r, r, n0, divisor_limb ); + } + return r; + } +} diff -uNr a/eucrypt/mpi/mpih-lshift.c b/eucrypt/mpi/mpih-lshift.c --- a/eucrypt/mpi/mpih-lshift.c false +++ b/eucrypt/mpi/mpih-lshift.c b4153b7f9f829152ca1273195628566628ca4eed54792c61cd58ec4481f83cded7e0a6dd4e1fb632b10b20314b28a209d2cf1f78a684a64f7a9002b6e00fb2b9 @@ -0,0 +1,64 @@ +/* mpihelp-lshift.c - MPI helper functions + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" + +/* Shift U (pointed to by UP and USIZE digits long) CNT bits to the left + * and store the USIZE least significant digits of the result at WP. + * Return the bits shifted out from the most significant digit. + * + * Argument constraints: + * 1. 0 < CNT < BITS_PER_MP_LIMB + * 2. If the result is to be written over the input, WP must be >= UP. + */ + +mpi_limb_t +mpihelp_lshift( mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, + unsigned int cnt) +{ + mpi_limb_t high_limb, low_limb; + unsigned sh_1, sh_2; + mpi_size_t i; + mpi_limb_t retval; + + sh_1 = cnt; + wp += 1; + sh_2 = BITS_PER_MPI_LIMB - sh_1; + i = usize - 1; + low_limb = up[i]; + retval = low_limb >> sh_2; + high_limb = low_limb; + while( --i >= 0 ) { + low_limb = up[i]; + wp[i] = (high_limb << sh_1) | (low_limb >> sh_2); + high_limb = low_limb; + } + wp[i] = high_limb << sh_1; + + return retval; +} + + diff -uNr a/eucrypt/mpi/mpih-mul.c b/eucrypt/mpi/mpih-mul.c --- a/eucrypt/mpi/mpih-mul.c false +++ b/eucrypt/mpi/mpih-mul.c 1c5bd39c13569d58a5cfd542d96df998b63efd14edfcdb9488975b69dd7796b21ef656577e9da950cece9d9122b7030395f0714cbba2983b3dafc860b34c1b85 @@ -0,0 +1,519 @@ +/* mpihelp-mul.c - MPI helper functions + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" +#include "longlong.h" + + +#define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \ + do { \ + if( (size) < KARATSUBA_THRESHOLD ) \ + mul_n_basecase (prodp, up, vp, size); \ + else \ + mul_n (prodp, up, vp, size, tspace); \ + } while (0); + +#define MPN_SQR_N_RECURSE(prodp, up, size, tspace) \ + do { \ + if ((size) < KARATSUBA_THRESHOLD) \ + mpih_sqr_n_basecase (prodp, up, size); \ + else \ + mpih_sqr_n (prodp, up, size, tspace); \ + } while (0); + + +/* Multiply the natural numbers u (pointed to by UP) and v (pointed to by VP), + * both with SIZE limbs, and store the result at PRODP. 2 * SIZE limbs are + * always stored. Return the most significant limb. + * + * Argument constraints: + * 1. PRODP != UP and PRODP != VP, i.e. the destination + * must be distinct from the multiplier and the multiplicand. + * + * + * Handle simple cases with traditional multiplication. + * + * This is the most critical code of multiplication. All multiplies rely + * on this, both small and huge. Small ones arrive here immediately. Huge + * ones arrive here as this is the base case for Karatsuba's recursive + * algorithm below. + */ + +static mpi_limb_t +mul_n_basecase( mpi_ptr_t prodp, mpi_ptr_t up, + mpi_ptr_t vp, mpi_size_t size) +{ + mpi_size_t i; + mpi_limb_t cy; + mpi_limb_t v_limb; + + /* Multiply by the first limb in V separately, as the result can be + * stored (not added) to PROD. We also avoid a loop for zeroing. */ + v_limb = vp[0]; + if( v_limb <= 1 ) { + if( v_limb == 1 ) + MPN_COPY( prodp, up, size ); + else + MPN_ZERO( prodp, size ); + cy = 0; + } + else + cy = mpihelp_mul_1( prodp, up, size, v_limb ); + + prodp[size] = cy; + prodp++; + + /* For each iteration in the outer loop, multiply one limb from + * U with one limb from V, and add it to PROD. */ + for( i = 1; i < size; i++ ) { + v_limb = vp[i]; + if( v_limb <= 1 ) { + cy = 0; + if( v_limb == 1 ) + cy = mpihelp_add_n(prodp, prodp, up, size); + } + else + cy = mpihelp_addmul_1(prodp, up, size, v_limb); + + prodp[size] = cy; + prodp++; + } + + return cy; +} + + +static void +mul_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp, + mpi_size_t size, mpi_ptr_t tspace ) +{ + if( size & 1 ) { + /* The size is odd, and the code below doesn't handle that. + * Multiply the least significant (size - 1) limbs with a recursive + * call, and handle the most significant limb of S1 and S2 + * separately. + * A slightly faster way to do this would be to make the Karatsuba + * code below behave as if the size were even, and let it check for + * odd size in the end. I.e., in essence move this code to the end. + * Doing so would save us a recursive call, and potentially make the + * stack grow a lot less. + */ + mpi_size_t esize = size - 1; /* even size */ + mpi_limb_t cy_limb; + + MPN_MUL_N_RECURSE( prodp, up, vp, esize, tspace ); + cy_limb = mpihelp_addmul_1( prodp + esize, up, esize, vp[esize] ); + prodp[esize + esize] = cy_limb; + cy_limb = mpihelp_addmul_1( prodp + esize, vp, size, up[esize] ); + prodp[esize + size] = cy_limb; + } + else { + /* Anatolij Alekseevich Karatsuba's divide-and-conquer algorithm. + * + * Split U in two pieces, U1 and U0, such that + * U = U0 + U1*(B**n), + * and V in V1 and V0, such that + * V = V0 + V1*(B**n). + * + * UV is then computed recursively using the identity + * + * 2n n n n + * UV = (B + B )U V + B (U -U )(V -V ) + (B + 1)U V + * 1 1 1 0 0 1 0 0 + * + * Where B = 2**BITS_PER_MP_LIMB. + */ + mpi_size_t hsize = size >> 1; + mpi_limb_t cy; + int negflg; + + /* Product H. ________________ ________________ + * |_____U1 x V1____||____U0 x V0_____| + * Put result in upper part of PROD and pass low part of TSPACE + * as new TSPACE. + */ + MPN_MUL_N_RECURSE(prodp + size, up + hsize, vp + hsize, hsize, tspace); + + /* Product M. ________________ + * |_(U1-U0)(V0-V1)_| + */ + if( mpihelp_cmp(up + hsize, up, hsize) >= 0 ) { + mpihelp_sub_n(prodp, up + hsize, up, hsize); + negflg = 0; + } + else { + mpihelp_sub_n(prodp, up, up + hsize, hsize); + negflg = 1; + } + if( mpihelp_cmp(vp + hsize, vp, hsize) >= 0 ) { + mpihelp_sub_n(prodp + hsize, vp + hsize, vp, hsize); + negflg ^= 1; + } + else { + mpihelp_sub_n(prodp + hsize, vp, vp + hsize, hsize); + /* No change of NEGFLG. */ + } + /* Read temporary operands from low part of PROD. + * Put result in low part of TSPACE using upper part of TSPACE + * as new TSPACE. + */ + MPN_MUL_N_RECURSE(tspace, prodp, prodp + hsize, hsize, tspace + size); + + /* Add/copy product H. */ + MPN_COPY (prodp + hsize, prodp + size, hsize); + cy = mpihelp_add_n( prodp + size, prodp + size, + prodp + size + hsize, hsize); + + /* Add product M (if NEGFLG M is a negative number) */ + if(negflg) + cy -= mpihelp_sub_n(prodp + hsize, prodp + hsize, tspace, size); + else + cy += mpihelp_add_n(prodp + hsize, prodp + hsize, tspace, size); + + /* Product L. ________________ ________________ + * |________________||____U0 x V0_____| + * Read temporary operands from low part of PROD. + * Put result in low part of TSPACE using upper part of TSPACE + * as new TSPACE. + */ + MPN_MUL_N_RECURSE(tspace, up, vp, hsize, tspace + size); + + /* Add/copy Product L (twice) */ + + cy += mpihelp_add_n(prodp + hsize, prodp + hsize, tspace, size); + if( cy ) + mpihelp_add_1(prodp + hsize + size, prodp + hsize + size, hsize, cy); + + MPN_COPY(prodp, tspace, hsize); + cy = mpihelp_add_n(prodp + hsize, prodp + hsize, tspace + hsize, hsize); + if( cy ) + mpihelp_add_1(prodp + size, prodp + size, size, 1); + } +} + + +void +mpih_sqr_n_basecase( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size ) +{ + mpi_size_t i; + mpi_limb_t cy_limb; + mpi_limb_t v_limb; + + /* Multiply by the first limb in V separately, as the result can be + * stored (not added) to PROD. We also avoid a loop for zeroing. */ + v_limb = up[0]; + if( v_limb <= 1 ) { + if( v_limb == 1 ) + MPN_COPY( prodp, up, size ); + else + MPN_ZERO(prodp, size); + cy_limb = 0; + } + else + cy_limb = mpihelp_mul_1( prodp, up, size, v_limb ); + + prodp[size] = cy_limb; + prodp++; + + /* For each iteration in the outer loop, multiply one limb from + * U with one limb from V, and add it to PROD. */ + for( i=1; i < size; i++) { + v_limb = up[i]; + if( v_limb <= 1 ) { + cy_limb = 0; + if( v_limb == 1 ) + cy_limb = mpihelp_add_n(prodp, prodp, up, size); + } + else + cy_limb = mpihelp_addmul_1(prodp, up, size, v_limb); + + prodp[size] = cy_limb; + prodp++; + } +} + + +void +mpih_sqr_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size, mpi_ptr_t tspace) +{ + if( size & 1 ) { + /* The size is odd, and the code below doesn't handle that. + * Multiply the least significant (size - 1) limbs with a recursive + * call, and handle the most significant limb of S1 and S2 + * separately. + * A slightly faster way to do this would be to make the Karatsuba + * code below behave as if the size were even, and let it check for + * odd size in the end. I.e., in essence move this code to the end. + * Doing so would save us a recursive call, and potentially make the + * stack grow a lot less. + */ + mpi_size_t esize = size - 1; /* even size */ + mpi_limb_t cy_limb; + + MPN_SQR_N_RECURSE( prodp, up, esize, tspace ); + cy_limb = mpihelp_addmul_1( prodp + esize, up, esize, up[esize] ); + prodp[esize + esize] = cy_limb; + cy_limb = mpihelp_addmul_1( prodp + esize, up, size, up[esize] ); + + prodp[esize + size] = cy_limb; + } + else { + mpi_size_t hsize = size >> 1; + mpi_limb_t cy; + + /* Product H. ________________ ________________ + * |_____U1 x U1____||____U0 x U0_____| + * Put result in upper part of PROD and pass low part of TSPACE + * as new TSPACE. + */ + MPN_SQR_N_RECURSE(prodp + size, up + hsize, hsize, tspace); + + /* Product M. ________________ + * |_(U1-U0)(U0-U1)_| + */ + if( mpihelp_cmp( up + hsize, up, hsize) >= 0 ) + mpihelp_sub_n( prodp, up + hsize, up, hsize); + else + mpihelp_sub_n (prodp, up, up + hsize, hsize); + + /* Read temporary operands from low part of PROD. + * Put result in low part of TSPACE using upper part of TSPACE + * as new TSPACE. */ + MPN_SQR_N_RECURSE(tspace, prodp, hsize, tspace + size); + + /* Add/copy product H */ + MPN_COPY(prodp + hsize, prodp + size, hsize); + cy = mpihelp_add_n(prodp + size, prodp + size, + prodp + size + hsize, hsize); + + /* Add product M (if NEGFLG M is a negative number). */ + cy -= mpihelp_sub_n (prodp + hsize, prodp + hsize, tspace, size); + + /* Product L. ________________ ________________ + * |________________||____U0 x U0_____| + * Read temporary operands from low part of PROD. + * Put result in low part of TSPACE using upper part of TSPACE + * as new TSPACE. */ + MPN_SQR_N_RECURSE (tspace, up, hsize, tspace + size); + + /* Add/copy Product L (twice). */ + cy += mpihelp_add_n (prodp + hsize, prodp + hsize, tspace, size); + if( cy ) + mpihelp_add_1(prodp + hsize + size, prodp + hsize + size, + hsize, cy); + + MPN_COPY(prodp, tspace, hsize); + cy = mpihelp_add_n (prodp + hsize, prodp + hsize, tspace + hsize, hsize); + if( cy ) + mpihelp_add_1 (prodp + size, prodp + size, size, 1); + } +} + + +/* This should be made into an inline function in gmp.h. */ +void +mpihelp_mul_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size) +{ + int secure; + + if( up == vp ) { + if( size < KARATSUBA_THRESHOLD ) + mpih_sqr_n_basecase( prodp, up, size ); + else { + mpi_ptr_t tspace; + secure = m_is_secure( up ); + tspace = mpi_alloc_limb_space( 2 * size, secure ); + mpih_sqr_n( prodp, up, size, tspace ); + mpi_free_limb_space( tspace ); + } + } + else { + if( size < KARATSUBA_THRESHOLD ) + mul_n_basecase( prodp, up, vp, size ); + else { + mpi_ptr_t tspace; + secure = m_is_secure( up ) || m_is_secure( vp ); + tspace = mpi_alloc_limb_space( 2 * size, secure ); + mul_n (prodp, up, vp, size, tspace); + mpi_free_limb_space( tspace ); + } + } +} + + + +void +mpihelp_mul_karatsuba_case( mpi_ptr_t prodp, + mpi_ptr_t up, mpi_size_t usize, + mpi_ptr_t vp, mpi_size_t vsize, + struct karatsuba_ctx *ctx ) +{ + mpi_limb_t cy; + + if( !ctx->tspace || ctx->tspace_size < vsize ) { + if( ctx->tspace ) + mpi_free_limb_space( ctx->tspace ); + ctx->tspace = mpi_alloc_limb_space( 2 * vsize, + m_is_secure( up ) || m_is_secure( vp ) ); + ctx->tspace_size = vsize; + } + + MPN_MUL_N_RECURSE( prodp, up, vp, vsize, ctx->tspace ); + + prodp += vsize; + up += vsize; + usize -= vsize; + if( usize >= vsize ) { + if( !ctx->tp || ctx->tp_size < vsize ) { + if( ctx->tp ) + mpi_free_limb_space( ctx->tp ); + ctx->tp = mpi_alloc_limb_space( 2 * vsize, m_is_secure( up ) + || m_is_secure( vp ) ); + ctx->tp_size = vsize; + } + + do { + MPN_MUL_N_RECURSE( ctx->tp, up, vp, vsize, ctx->tspace ); + cy = mpihelp_add_n( prodp, prodp, ctx->tp, vsize ); + mpihelp_add_1( prodp + vsize, ctx->tp + vsize, vsize, cy ); + prodp += vsize; + up += vsize; + usize -= vsize; + } while( usize >= vsize ); + } + + if( usize ) { + if( usize < KARATSUBA_THRESHOLD ) { + mpihelp_mul( ctx->tspace, vp, vsize, up, usize ); + } + else { + if( !ctx->next ) { + ctx->next = xmalloc_clear( sizeof *ctx ); + } + mpihelp_mul_karatsuba_case( ctx->tspace, + vp, vsize, + up, usize, + ctx->next ); + } + + cy = mpihelp_add_n( prodp, prodp, ctx->tspace, vsize); + mpihelp_add_1( prodp + vsize, ctx->tspace + vsize, usize, cy ); + } +} + + +void +mpihelp_release_karatsuba_ctx( struct karatsuba_ctx *ctx ) +{ + struct karatsuba_ctx *ctx2; + + if( ctx->tp ) + mpi_free_limb_space( ctx->tp ); + if( ctx->tspace ) + mpi_free_limb_space( ctx->tspace ); + for( ctx=ctx->next; ctx; ctx = ctx2 ) { + ctx2 = ctx->next; + if( ctx->tp ) + mpi_free_limb_space( ctx->tp ); + if( ctx->tspace ) + mpi_free_limb_space( ctx->tspace ); + xfree( ctx ); + } +} + +/* Multiply the natural numbers u (pointed to by UP, with USIZE limbs) + * and v (pointed to by VP, with VSIZE limbs), and store the result at + * PRODP. USIZE + VSIZE limbs are always stored, but if the input + * operands are normalized. Return the most significant limb of the + * result. + * + * NOTE: The space pointed to by PRODP is overwritten before finished + * with U and V, so overlap is an error. + * + * Argument constraints: + * 1. USIZE >= VSIZE. + * 2. PRODP != UP and PRODP != VP, i.e. the destination + * must be distinct from the multiplier and the multiplicand. + */ + +mpi_limb_t +mpihelp_mul( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize, + mpi_ptr_t vp, mpi_size_t vsize) +{ + mpi_ptr_t prod_endp = prodp + usize + vsize - 1; + mpi_limb_t cy; + struct karatsuba_ctx ctx; + + if( vsize < KARATSUBA_THRESHOLD ) { + mpi_size_t i; + mpi_limb_t v_limb; + + if( !vsize ) + return 0; + + /* Multiply by the first limb in V separately, as the result can be + * stored (not added) to PROD. We also avoid a loop for zeroing. */ + v_limb = vp[0]; + if( v_limb <= 1 ) { + if( v_limb == 1 ) + MPN_COPY( prodp, up, usize ); + else + MPN_ZERO( prodp, usize ); + cy = 0; + } + else + cy = mpihelp_mul_1( prodp, up, usize, v_limb ); + + prodp[usize] = cy; + prodp++; + + /* For each iteration in the outer loop, multiply one limb from + * U with one limb from V, and add it to PROD. */ + for( i = 1; i < vsize; i++ ) { + v_limb = vp[i]; + if( v_limb <= 1 ) { + cy = 0; + if( v_limb == 1 ) + cy = mpihelp_add_n(prodp, prodp, up, usize); + } + else + cy = mpihelp_addmul_1(prodp, up, usize, v_limb); + + prodp[usize] = cy; + prodp++; + } + + return cy; + } + + memset( &ctx, 0, sizeof ctx ); + mpihelp_mul_karatsuba_case( prodp, up, usize, vp, vsize, &ctx ); + mpihelp_release_karatsuba_ctx( &ctx ); + return *prod_endp; +} + + diff -uNr a/eucrypt/mpi/mpih-mul1.c b/eucrypt/mpi/mpih-mul1.c --- a/eucrypt/mpi/mpih-mul1.c false +++ b/eucrypt/mpi/mpih-mul1.c 2fcc124504adc576636a56bc387f7f6b73c60b263ed01a7dffa2c2131f89aa6d337399ef9db92c5423d25ba596a898ad1160ac1eab5d49768aeab14d08c29466 @@ -0,0 +1,56 @@ +/* mpihelp-mul_1.c - MPI helper functions + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" +#include "longlong.h" + +mpi_limb_t +mpihelp_mul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size, + mpi_limb_t s2_limb) +{ + mpi_limb_t cy_limb; + mpi_size_t j; + mpi_limb_t prod_high, prod_low; + + /* The loop counter and index J goes from -S1_SIZE to -1. This way + * the loop becomes faster. */ + j = -s1_size; + + /* Offset the base pointers to compensate for the negative indices. */ + s1_ptr -= j; + res_ptr -= j; + + cy_limb = 0; + do { + umul_ppmm( prod_high, prod_low, s1_ptr[j], s2_limb ); + prod_low += cy_limb; + cy_limb = (prod_low < cy_limb?1:0) + prod_high; + res_ptr[j] = prod_low; + } while( ++j ); + + return cy_limb; +} + diff -uNr a/eucrypt/mpi/mpih-mul2.c b/eucrypt/mpi/mpih-mul2.c --- a/eucrypt/mpi/mpih-mul2.c false +++ b/eucrypt/mpi/mpih-mul2.c 3b4cc6335137ae38d7a62b34e1d2319c33371d77b6169ab101b4df8ce83ee7e10ff859f24626b13ae42aff8cffc805ffaa433d53faf56c5924837ac1fac0a6f9 @@ -0,0 +1,61 @@ +/* mpihelp-mul_2.c - MPI helper functions + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" +#include "longlong.h" + + +mpi_limb_t +mpihelp_addmul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_size_t s1_size, mpi_limb_t s2_limb) +{ + mpi_limb_t cy_limb; + mpi_size_t j; + mpi_limb_t prod_high, prod_low; + mpi_limb_t x; + + /* The loop counter and index J goes from -SIZE to -1. This way + * the loop becomes faster. */ + j = -s1_size; + res_ptr -= j; + s1_ptr -= j; + + cy_limb = 0; + do { + umul_ppmm( prod_high, prod_low, s1_ptr[j], s2_limb ); + + prod_low += cy_limb; + cy_limb = (prod_low < cy_limb?1:0) + prod_high; + + x = res_ptr[j]; + prod_low = x + prod_low; + cy_limb += prod_low < x?1:0; + res_ptr[j] = prod_low; + } while ( ++j ); + return cy_limb; +} + + diff -uNr a/eucrypt/mpi/mpih-mul3.c b/eucrypt/mpi/mpih-mul3.c --- a/eucrypt/mpi/mpih-mul3.c false +++ b/eucrypt/mpi/mpih-mul3.c a6703d0851fb4f5a7c05ea94b0ea1c9df3b79379b43c55ef10481496984dc6b58c3b26fc009607ede37917758cc7576065049c5a511eee7e0b9048e1a1b06654 @@ -0,0 +1,62 @@ +/* mpihelp-mul_3.c - MPI helper functions + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" +#include "longlong.h" + + +mpi_limb_t +mpihelp_submul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_size_t s1_size, mpi_limb_t s2_limb) +{ + mpi_limb_t cy_limb; + mpi_size_t j; + mpi_limb_t prod_high, prod_low; + mpi_limb_t x; + + /* The loop counter and index J goes from -SIZE to -1. This way + * the loop becomes faster. */ + j = -s1_size; + res_ptr -= j; + s1_ptr -= j; + + cy_limb = 0; + do { + umul_ppmm( prod_high, prod_low, s1_ptr[j], s2_limb); + + prod_low += cy_limb; + cy_limb = (prod_low < cy_limb?1:0) + prod_high; + + x = res_ptr[j]; + prod_low = x - prod_low; + cy_limb += prod_low > x?1:0; + res_ptr[j] = prod_low; + } while( ++j ); + + return cy_limb; +} + + diff -uNr a/eucrypt/mpi/mpih-rshift.c b/eucrypt/mpi/mpih-rshift.c --- a/eucrypt/mpi/mpih-rshift.c false +++ b/eucrypt/mpi/mpih-rshift.c fb51d6b55d5e9b7ada61ce8c50c3958a5d8b38cd1673683437d572ef52469c428a68c2926739eee75ef379db77c713f4bd8506b53a7e259e2ce9516e23ac44ef @@ -0,0 +1,62 @@ +/* mpih-rshift.c - MPI helper functions + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" + + +/* Shift U (pointed to by UP and USIZE limbs long) CNT bits to the right + * and store the USIZE least significant limbs of the result at WP. + * The bits shifted out to the right are returned. + * + * Argument constraints: + * 1. 0 < CNT < BITS_PER_MP_LIMB + * 2. If the result is to be written over the input, WP must be <= UP. + */ + +mpi_limb_t +mpihelp_rshift( mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, unsigned cnt) +{ + mpi_limb_t high_limb, low_limb; + unsigned sh_1, sh_2; + mpi_size_t i; + mpi_limb_t retval; + + sh_1 = cnt; + wp -= 1; + sh_2 = BITS_PER_MPI_LIMB - sh_1; + high_limb = up[0]; + retval = high_limb << sh_2; + low_limb = high_limb; + for( i=1; i < usize; i++) { + high_limb = up[i]; + wp[i] = (low_limb >> sh_1) | (high_limb << sh_2); + low_limb = high_limb; + } + wp[i] = low_limb >> sh_1; + + return retval; +} + diff -uNr a/eucrypt/mpi/mpih-sub1.c b/eucrypt/mpi/mpih-sub1.c --- a/eucrypt/mpi/mpih-sub1.c false +++ b/eucrypt/mpi/mpih-sub1.c 88c8dfd8a7cbbc742fe8e01121c9166dc010ba16554277137ece7642bb6c9d94183ea6d23f4118d2bcd7a2a31a399a22a7a264ea178c0ce0bd4a2d0bf18f149f @@ -0,0 +1,60 @@ +/* mpihelp-add_2.c - MPI helper functions + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include + +#include "knobs.h" +#include "mpi-internal.h" +#include "longlong.h" + +mpi_limb_t +mpihelp_sub_n( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_ptr_t s2_ptr, mpi_size_t size) +{ + mpi_limb_t x, y, cy; + mpi_size_t j; + + /* The loop counter and index J goes from -SIZE to -1. This way + the loop becomes faster. */ + j = -size; + + /* Offset the base pointers to compensate for the negative indices. */ + s1_ptr -= j; + s2_ptr -= j; + res_ptr -= j; + + cy = 0; + do { + y = s2_ptr[j]; + x = s1_ptr[j]; + y += cy; /* add previous carry to subtrahend */ + cy = y < cy; /* get out carry from that addition */ + y = x - y; /* main subtract */ + cy += y > x; /* get out carry from the subtract, combine */ + res_ptr[j] = y; + } while( ++j ); + + return cy; +} + + diff -uNr a/eucrypt/mpi/mpiutil.c b/eucrypt/mpi/mpiutil.c --- a/eucrypt/mpi/mpiutil.c false +++ b/eucrypt/mpi/mpiutil.c 4f010f44b2944a2995791c5a74d41bc1ffbe017c6bcbcefa0655dd33c72cfc6aa547b7bceda6705c629ab707bbd2f260023efae997dd1ec53fd016d22fe1d5f5 @@ -0,0 +1,508 @@ +/* mpiutil.ac - Utility functions for MPI + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include +#include +#include + +#include "knobs.h" +#include "mpi.h" +#include "mpi-internal.h" +#include "memory.h" +#include "util.h" + + +#ifdef M_DEBUG +#undef mpi_alloc +#undef mpi_alloc_secure +#undef mpi_free +#endif + +/**************** + * Note: It was a bad idea to use the number of limbs to allocate + * because on a alpha the limbs are large but we normally need + * integers of n bits - So we should chnage this to bits (or bytes). + * + * But mpi_alloc is used in a lot of places :-) + */ +MPI +#ifdef M_DEBUG +mpi_debug_alloc( unsigned nlimbs, const char *info ) +#else +mpi_alloc( unsigned nlimbs ) +#endif +{ + MPI a; + + if( DBG_MEMORY ) + log_debug("mpi_alloc(%u)\n", nlimbs*BITS_PER_MPI_LIMB ); +#ifdef M_DEBUG + a = m_debug_alloc( sizeof *a, info ); + a->d = nlimbs? mpi_debug_alloc_limb_space( nlimbs, 0, info ) : NULL; +#else + a = xmalloc( sizeof *a ); + a->d = nlimbs? mpi_alloc_limb_space( nlimbs, 0 ) : NULL; +#endif + a->alloced = nlimbs; + a->nlimbs = 0; + a->sign = 0; + a->flags = 0; + a->nbits = 0; + return a; +} + +void +mpi_m_check( MPI a ) +{ + m_check(a); + m_check(a->d); +} + +MPI +#ifdef M_DEBUG +mpi_debug_alloc_secure( unsigned nlimbs, const char *info ) +#else +mpi_alloc_secure( unsigned nlimbs ) +#endif +{ + MPI a; + + if( DBG_MEMORY ) + log_debug("mpi_alloc_secure(%u)\n", nlimbs*BITS_PER_MPI_LIMB ); +#ifdef M_DEBUG + a = m_debug_alloc( sizeof *a, info ); + a->d = nlimbs? mpi_debug_alloc_limb_space( nlimbs, 1, info ) : NULL; +#else + a = xmalloc( sizeof *a ); + a->d = nlimbs? mpi_alloc_limb_space( nlimbs, 1 ) : NULL; +#endif + a->alloced = nlimbs; + a->flags = 1; + a->nlimbs = 0; + a->sign = 0; + a->nbits = 0; + return a; +} + + +#if 0 +static void *unused_limbs_5; +static void *unused_limbs_32; +static void *unused_limbs_64; +#endif + +mpi_ptr_t +#ifdef M_DEBUG +mpi_debug_alloc_limb_space( unsigned nlimbs, int secure, const char *info ) +#else +mpi_alloc_limb_space( unsigned nlimbs, int secure ) +#endif +{ + size_t len = nlimbs * sizeof(mpi_limb_t); + mpi_ptr_t p; + + if( DBG_MEMORY ) + log_debug("mpi_alloc_limb_space(%u)\n", (unsigned)len*8 ); +#if 0 + if( !secure ) { + if( nlimbs == 5 && unused_limbs_5 ) { /* DSA 160 bits */ + p = unused_limbs_5; + unused_limbs_5 = *p; + return p; + } + else if( nlimbs == 32 && unused_limbs_32 ) { /* DSA 1024 bits */ + p = unused_limbs_32; + unused_limbs_32 = *p; + return p; + } + else if( nlimbs == 64 && unused_limbs_64 ) { /* DSA 2*1024 bits */ + p = unused_limbs_64; + unused_limbs_64 = *p; + return p; + } + } +#endif + +#ifdef M_DEBUG + p = secure? m_debug_alloc_secure(len, info):m_debug_alloc( len, info ); +#else + p = secure? xmalloc_secure( len ):xmalloc( len ); +#endif + + return p; +} + +void +#ifdef M_DEBUG +mpi_debug_free_limb_space( mpi_ptr_t a, const char *info ) +#else +mpi_free_limb_space( mpi_ptr_t a ) +#endif +{ + if( !a ) + return; + if( DBG_MEMORY ) + log_debug("mpi_free_limb_space of size %lu\n", (ulong)m_size(a)*8 ); + +#if 0 + if( !m_is_secure(a) ) { + size_t nlimbs = m_size(a) / 4 ; + void *p = a; + + if( nlimbs == 5 ) { /* DSA 160 bits */ + *a = unused_limbs_5; + unused_limbs_5 = a; + return; + } + else if( nlimbs == 32 ) { /* DSA 1024 bits */ + *a = unused_limbs_32; + unused_limbs_32 = a; + return; + } + else if( nlimbs == 64 ) { /* DSA 2*1024 bits */ + *a = unused_limbs_64; + unused_limbs_64 = a; + return; + } + } +#endif + + xfree(a); +} + + +void +mpi_assign_limb_space( MPI a, mpi_ptr_t ap, unsigned nlimbs ) +{ + mpi_free_limb_space(a->d); + a->d = ap; + a->alloced = nlimbs; +} + + + +/**************** + * Resize the array of A to NLIMBS. the additional space is cleared + * (set to 0) [done by xrealloc()] + */ +void +#ifdef M_DEBUG +mpi_debug_resize( MPI a, unsigned nlimbs, const char *info ) +#else +mpi_resize( MPI a, unsigned nlimbs ) +#endif +{ + if( nlimbs <= a->alloced ) + return; /* no need to do it */ + /* Note: a->secure is not used - instead the realloc functions + * take care of it. Maybe we should drop a->secure completely + * and rely on a mpi_is_secure function, which would be + * a wrapper around m_is_secure + */ +#ifdef M_DEBUG + if( a->d ) + a->d = m_debug_realloc(a->d, nlimbs * sizeof(mpi_limb_t), info ); + else + a->d = m_debug_alloc_clear( nlimbs * sizeof(mpi_limb_t), info ); +#else + if( a->d ) + a->d = xrealloc(a->d, nlimbs * sizeof(mpi_limb_t) ); + else + a->d = xmalloc_clear( nlimbs * sizeof(mpi_limb_t) ); +#endif + a->alloced = nlimbs; +} + +void +mpi_clear( MPI a ) +{ + a->nlimbs = 0; + a->nbits = 0; + a->flags = 0; +} + + +void +#ifdef M_DEBUG +mpi_debug_free( MPI a, const char *info ) +#else +mpi_free( MPI a ) +#endif +{ + if( !a ) + return; + if( DBG_MEMORY ) + log_debug("mpi_free\n" ); + if( a->flags & 4 ) + xfree( a->d ); + else { +#ifdef M_DEBUG + mpi_debug_free_limb_space(a->d, info); +#else + mpi_free_limb_space(a->d); +#endif + } + if( a->flags & ~7 ) + log_bug("invalid flag value in mpi\n"); + xfree(a); +} + + +void +mpi_set_secure( MPI a ) +{ + mpi_ptr_t ap, bp; + + if( (a->flags & 1) ) + return; + a->flags |= 1; + ap = a->d; + if( !a->nlimbs ) { + assert(!ap); + return; + } +#ifdef M_DEBUG + bp = mpi_debug_alloc_limb_space( a->nlimbs, 1, "set_secure" ); +#else + bp = mpi_alloc_limb_space( a->nlimbs, 1 ); +#endif + MPN_COPY( bp, ap, a->nlimbs ); + a->d = bp; +#ifdef M_DEBUG + mpi_debug_free_limb_space(ap, "set_secure"); +#else + mpi_free_limb_space(ap); +#endif +} + + +MPI +mpi_set_opaque( MPI a, void *p, unsigned int len ) +{ + if( !a ) { +#ifdef M_DEBUG + a = mpi_debug_alloc(0,"alloc_opaque"); +#else + a = mpi_alloc(0); +#endif + } + + if( a->flags & 4 ) + xfree( a->d ); + else { +#ifdef M_DEBUG + mpi_debug_free_limb_space(a->d, "alloc_opaque"); +#else + mpi_free_limb_space(a->d); +#endif + } + + a->d = p; + a->alloced = 0; + a->nlimbs = 0; + a->nbits = len; + a->flags = 4; + return a; +} + + +void * +mpi_get_opaque( MPI a, unsigned int *len ) +{ + if( !(a->flags & 4) ) + log_bug("mpi_get_opaque on normal mpi\n"); + if( len ) + *len = a->nbits; + return a->d; +} + + +/**************** + * Note: This copy function should not interpret the MPI + * but copy it transparently. + */ +MPI +#ifdef M_DEBUG +mpi_debug_copy( MPI a, const char *info ) +#else +mpi_copy( MPI a ) +#endif +{ + int i; + MPI b; + + if( a && (a->flags & 4) ) { + void *p = m_is_secure(a->d)? xmalloc_secure( a->nbits ) + : xmalloc( a->nbits ); + memcpy( p, a->d, a->nbits ); + b = mpi_set_opaque( NULL, p, a->nbits ); + } + else if( a ) { +#ifdef M_DEBUG + b = mpi_is_secure(a)? mpi_debug_alloc_secure( a->nlimbs, info ) + : mpi_debug_alloc( a->nlimbs, info ); +#else + b = mpi_is_secure(a)? mpi_alloc_secure( a->nlimbs ) + : mpi_alloc( a->nlimbs ); +#endif + b->nlimbs = a->nlimbs; + b->sign = a->sign; + b->flags = a->flags; + b->nbits = a->nbits; + for(i=0; i < b->nlimbs; i++ ) + b->d[i] = a->d[i]; + } + else + b = NULL; + return b; +} + + +/**************** + * This function allocates an MPI which is optimized to hold + * a value as large as the one given in the argument and allocates it + * with the same flags as A. + */ +MPI +#ifdef M_DEBUG +mpi_debug_alloc_like( MPI a, const char *info ) +#else +mpi_alloc_like( MPI a ) +#endif +{ + MPI b; + + if( a && (a->flags & 4) ) { + void *p = m_is_secure(a->d)? xmalloc_secure( a->nbits ) + : xmalloc( a->nbits ); + memcpy( p, a->d, a->nbits ); + b = mpi_set_opaque( NULL, p, a->nbits ); + } + else if( a ) { +#ifdef M_DEBUG + b = mpi_is_secure(a)? mpi_debug_alloc_secure( a->nlimbs, info ) + : mpi_debug_alloc( a->nlimbs, info ); +#else + b = mpi_is_secure(a)? mpi_alloc_secure( a->nlimbs ) + : mpi_alloc( a->nlimbs ); +#endif + b->nlimbs = 0; + b->sign = 0; + b->flags = a->flags; + b->nbits = 0; + } + else + b = NULL; + return b; +} + + +void +mpi_set( MPI w, MPI u) +{ + mpi_ptr_t wp, up; + mpi_size_t usize = u->nlimbs; + int usign = u->sign; + + RESIZE_IF_NEEDED(w, usize); + wp = w->d; + up = u->d; + MPN_COPY( wp, up, usize ); + w->nlimbs = usize; + w->nbits = u->nbits; + w->flags = u->flags; + w->sign = usign; +} + + +void +mpi_set_ui( MPI w, unsigned long u) +{ + RESIZE_IF_NEEDED(w, 1); + w->d[0] = u; + w->nlimbs = u? 1:0; + w->sign = 0; + w->nbits = 0; + w->flags = 0; +} + + +MPI +mpi_alloc_set_ui( unsigned long u) +{ +#ifdef M_DEBUG + MPI w = mpi_debug_alloc(1,"alloc_set_ui"); +#else + MPI w = mpi_alloc(1); +#endif + w->d[0] = u; + w->nlimbs = u? 1:0; + w->sign = 0; + return w; +} + + +void +mpi_swap( MPI a, MPI b) +{ + struct gcry_mpi tmp; + + tmp = *a; *a = *b; *b = tmp; +} + + +int +mpi_get_nlimbs (MPI a) +{ + return a->nlimbs; +} + + +int +mpi_is_neg (MPI a) +{ + return a->sign; +} + + +/* Return the number of limbs to store an MPI which is specified by + the number of bytes to represent it. */ +unsigned int +mpi_nlimb_hint_from_nbytes (unsigned int nbytes) +{ + return (nbytes+BYTES_PER_MPI_LIMB-1) / BYTES_PER_MPI_LIMB; +} + +/* Return the number of limbs to store an MPI which is specified by + the number of bytes to represent it. */ +unsigned int +mpi_nlimb_hint_from_nbits (unsigned int nbits) +{ + return (nbits+BITS_PER_MPI_LIMB-1) / BITS_PER_MPI_LIMB; +} + +unsigned int +mpi_get_flags (MPI a) +{ + return a->flags; +} diff -uNr a/eucrypt/mpi/obj/README b/eucrypt/mpi/obj/README --- a/eucrypt/mpi/obj/README false +++ b/eucrypt/mpi/obj/README a2dfde45e25a7451ba7b26d345c4a422883a52d65b3f54d5890cd3e5b5d57e50c74f87ae20831d160f9e061500acd8775f61c5984e8d9370c308c7a3c34c2145 @@ -0,0 +1 @@ +obj \ No newline at end of file diff -uNr a/eucrypt/mpi/secmem.c b/eucrypt/mpi/secmem.c --- a/eucrypt/mpi/secmem.c false +++ b/eucrypt/mpi/secmem.c 2b787a241ab819008b23b6235aec68ea7ea5dc092859ff42ffe50a7bd00d710f39547e35ee66449377fe70bdd870f7bd4b40b7ede228f6842671c5e167183493 @@ -0,0 +1,511 @@ +/* secmem.c - memory allocation from a secure heap + * Modified by No Such Labs. (C) 2015. See README. + * + * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10, + * SHA256(gnupg-1.4.10.tar.gz): + * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a + * (C) 1994-2005 Free Software Foundation, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include "knobs.h" + +#include +#include +#include +#include +#include +#include +#if defined(HAVE_MLOCK) || defined(HAVE_MMAP) +#include +#include +#include +#ifdef USE_CAPABILITIES +#include +#endif +#ifdef HAVE_PLOCK +#include +#endif +#endif + +#include "types.h" +#include "memory.h" +#include "util.h" + +/* MinGW doesn't seem to prototype getpagesize, though it does have + it. */ +#if !HAVE_DECL_GETPAGESIZE +int getpagesize(void); +#endif + +#if defined(MAP_ANON) && !defined(MAP_ANONYMOUS) +#define MAP_ANONYMOUS MAP_ANON +#endif +/* It seems that Slackware 7.1 does not know about EPERM */ +#if !defined(EPERM) && defined(ENOMEM) +#define EPERM ENOMEM +#endif + + +#define DEFAULT_POOLSIZE 16384 + +typedef struct memblock_struct MEMBLOCK; +struct memblock_struct { + unsigned size; + union { + MEMBLOCK *next; + PROPERLY_ALIGNED_TYPE aligned; + } u; +}; + + + +static void *pool; +static volatile int pool_okay; /* may be checked in an atexit function */ +#ifdef HAVE_MMAP +static volatile int pool_is_mmapped; +#endif +static size_t poolsize; /* allocated length */ +static size_t poollen; /* used length */ +static MEMBLOCK *unused_blocks; +static unsigned max_alloced; +static unsigned cur_alloced; +static unsigned max_blocks; +static unsigned cur_blocks; +static int disable_secmem; +static int show_warning; +static int no_warning; +static int suspend_warning; + + +static void +print_warn(void) +{ + if (!no_warning) + { + log_info("WARNING: using insecure memory!\n"); + } +} + + +static void +lock_pool( void *p, size_t n ) +{ +#if defined(USE_CAPABILITIES) && defined(HAVE_MLOCK) + int err; + + cap_set_proc( cap_from_text("cap_ipc_lock+ep") ); + err = mlock( p, n ); + if( err && errno ) + err = errno; + cap_set_proc( cap_from_text("cap_ipc_lock+p") ); + + if( err ) { + if( errno != EPERM +#ifdef EAGAIN /* OpenBSD returns this */ + && errno != EAGAIN +#endif +#ifdef ENOSYS /* Some SCOs return this (function not implemented) */ + && errno != ENOSYS +#endif +#ifdef ENOMEM /* Linux can return this */ + && errno != ENOMEM +#endif + ) + log_error("can't lock memory: %s\n", strerror(err)); + show_warning = 1; + } + +#elif defined(HAVE_MLOCK) + uid_t uid; + int err; + + uid = getuid(); + +#ifdef HAVE_BROKEN_MLOCK + /* ick. but at least we get secured memory. about to lock + entire data segment. */ +#ifdef HAVE_PLOCK +# ifdef _AIX + /* The configure for AIX returns broken mlock but the plock has + the strange requirement to somehow set the stack limit first. + The problem might turn out in indeterministic program behaviour + and hanging processes which can somehow be solved when enough + processes are clogging up the memory. To get this problem out + of the way we simply don't try to lock the memory at all. + */ + errno = EPERM; + err = errno; +# else /* !_AIX */ + err = plock( DATLOCK ); + if( err && errno ) + err = errno; +# endif /*_AIX*/ +#else /*!HAVE_PLOCK*/ + if( uid ) { + errno = EPERM; + err = errno; + } + else { + err = mlock( p, n ); + if( err && errno ) + err = errno; + } +#endif /*!HAVE_PLOCK*/ +#else + err = mlock( p, n ); + if( err && errno ) + err = errno; +#endif + + if( uid && !geteuid() ) { + /* check that we really dropped the privs. + * Note: setuid(0) should always fail */ + if( setuid( uid ) || getuid() != geteuid() || !setuid(0) ) + log_fatal("failed to reset uid: %s\n", strerror(errno)); + } + + if( err ) { + if( errno != EPERM +#ifdef EAGAIN /* OpenBSD returns this */ + && errno != EAGAIN +#endif +#ifdef ENOSYS /* Some SCOs return this (function not implemented) */ + && errno != ENOSYS +#endif +#ifdef ENOMEM /* Linux can return this */ + && errno != ENOMEM +#endif + ) + log_error("can't lock memory: %s\n", strerror(err)); + show_warning = 1; + } + +#elif defined ( __QNX__ ) + /* QNX does not page at all, so the whole secure memory stuff does + * not make much sense. However it is still of use because it + * wipes out the memory on a free(). + * Therefore it is sufficient to suppress the warning + */ +#elif defined (HAVE_DOSISH_SYSTEM) || defined (__CYGWIN__) + /* It does not make sense to print such a warning, given the fact that + * this whole Windows !@#$% and their user base are inherently insecure + */ +#else + log_info("Please note that you don't have secure memory on this system\n"); +#endif +} + + +static void +init_pool( size_t n) +{ + long int pgsize_val; + size_t pgsize; + + poolsize = n; + + if( disable_secmem ) + log_bug("secure memory is disabled"); + +#if defined(HAVE_SYSCONF) && defined(_SC_PAGESIZE) + pgsize_val = sysconf (_SC_PAGESIZE); +#elif defined(HAVE_GETPAGESIZE) + pgsize_val = getpagesize (); +#else + pgsize_val = -1; +#endif + pgsize = (pgsize_val != -1 && pgsize_val > 0)? pgsize_val : 4096; + + +#ifdef HAVE_MMAP + poolsize = (poolsize + pgsize -1 ) & ~(pgsize-1); +#ifdef MAP_ANONYMOUS + pool = mmap( 0, poolsize, PROT_READ|PROT_WRITE, + MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); +#else /* map /dev/zero instead */ + { int fd; + + fd = open("/dev/zero", O_RDWR); + if( fd == -1 ) { + log_error("can't open /dev/zero: %s\n", strerror(errno) ); + pool = (void*)-1; + } + else { + pool = mmap( 0, poolsize, PROT_READ|PROT_WRITE, + MAP_PRIVATE, fd, 0); + close (fd); + } + } +#endif + if( pool == (void*)-1 ) + log_info("can't mmap pool of %u bytes: %s - using malloc\n", + (unsigned)poolsize, strerror(errno)); + else { + pool_is_mmapped = 1; + pool_okay = 1; + } + +#endif + if( !pool_okay ) { + pool = malloc( poolsize ); + if( !pool ) + log_fatal("can't allocate memory pool of %u bytes\n", + (unsigned)poolsize); + else + pool_okay = 1; + } + lock_pool( pool, poolsize ); + poollen = 0; +} + + +/* concatenate unused blocks */ +static void +compress_pool(void) +{ + /* fixme: we really should do this */ +} + +void +secmem_set_flags( unsigned flags ) +{ + int was_susp = suspend_warning; + + no_warning = flags & 1; + suspend_warning = flags & 2; + + /* and now issue the warning if it is not longer suspended */ + if( was_susp && !suspend_warning && show_warning ) { + show_warning = 0; + print_warn(); + } +} + +unsigned +secmem_get_flags(void) +{ + unsigned flags; + + flags = no_warning ? 1:0; + flags |= suspend_warning ? 2:0; + return flags; +} + +/* Returns 1 if memory was locked, 0 if not. */ +int +secmem_init( size_t n ) +{ + if( !n ) { +#ifdef USE_CAPABILITIES + /* drop all capabilities */ + cap_set_proc( cap_from_text("all-eip") ); +#elif !defined(HAVE_DOSISH_SYSTEM) + uid_t uid; + disable_secmem=1; + uid = getuid(); + if( uid != geteuid() ) { + if( setuid( uid ) || getuid() != geteuid() || !setuid(0) ) + log_fatal("failed to drop setuid\n" ); + } +#endif + } + else { + if( n < DEFAULT_POOLSIZE ) + n = DEFAULT_POOLSIZE; + if( !pool_okay ) + init_pool(n); + else + log_error("Oops, secure memory pool already initialized\n"); + } + + return !show_warning; +} + + +void * +secmem_malloc( size_t size ) +{ + MEMBLOCK *mb, *mb2; + int compressed=0; + + if( !pool_okay ) { + log_info( + "operation is not possible without initialized secure memory\n"); + log_info("(you may have used the wrong program for this task)\n"); + exit(2); + } + if( show_warning && !suspend_warning ) { + show_warning = 0; + print_warn(); + } + + /* Blocks are always a multiple of 32. Note that we allocate an + extra of the size of an entire MEMBLOCK. This is required + becuase we do not only need the SIZE info but also extra space + to chain up unused memory blocks. */ + size += sizeof(MEMBLOCK); + size = ((size + 31) / 32) * 32; + + retry: + /* try to get it from the used blocks */ + for(mb = unused_blocks,mb2=NULL; mb; mb2=mb, mb = mb->u.next ) + if( mb->size >= size ) { + if( mb2 ) + mb2->u.next = mb->u.next; + else + unused_blocks = mb->u.next; + goto leave; + } + /* allocate a new block */ + if( (poollen + size <= poolsize) ) { + mb = (void*)((char*)pool + poollen); + poollen += size; + mb->size = size; + } + else if( !compressed ) { + compressed=1; + compress_pool(); + goto retry; + } + else + return NULL; + + leave: + cur_alloced += mb->size; + cur_blocks++; + if( cur_alloced > max_alloced ) + max_alloced = cur_alloced; + if( cur_blocks > max_blocks ) + max_blocks = cur_blocks; + + return &mb->u.aligned.c; +} + + +void * +secmexrealloc( void *p, size_t newsize ) +{ + MEMBLOCK *mb; + size_t size; + void *a; + + mb = (MEMBLOCK*)((char*)p - ((size_t) &((MEMBLOCK*)0)->u.aligned.c)); + size = mb->size; + if (size < sizeof(MEMBLOCK)) + log_bug ("secure memory corrupted at block %p\n", (void *)mb); + size -= ((size_t) &((MEMBLOCK*)0)->u.aligned.c); + + if( newsize <= size ) + return p; /* It is easier not to shrink the memory. */ + a = secmem_malloc( newsize ); + if ( a ) { + memcpy(a, p, size); + memset((char*)a+size, 0, newsize-size); + secmem_free(p); + } + return a; +} + + +void +secmem_free( void *a ) +{ + MEMBLOCK *mb; + size_t size; + + if( !a ) + return; + + mb = (MEMBLOCK*)((char*)a - ((size_t) &((MEMBLOCK*)0)->u.aligned.c)); + size = mb->size; + /* This does not make much sense: probably this memory is held in the + * cache. We do it anyway: */ + wipememory2(mb, 0xff, size ); + wipememory2(mb, 0xaa, size ); + wipememory2(mb, 0x55, size ); + wipememory2(mb, 0x00, size ); + mb->size = size; + mb->u.next = unused_blocks; + unused_blocks = mb; + cur_blocks--; + cur_alloced -= size; +} + + +/* Check whether P points into the pool. */ +static int +ptr_into_pool_p (const void *p) +{ + /* We need to convert pointers to addresses. This is required by + C-99 6.5.8 to avoid undefined behaviour. Using size_t is at + least only implementation defined. See also + http://lists.gnupg.org/pipermail/gcrypt-devel/2007-February/001102.html + */ + size_t p_addr = (size_t)p; + size_t pool_addr = (size_t)pool; + + return p_addr >= pool_addr && p_addr < pool_addr+poolsize; +} + + +int +m_is_secure( const void *p ) +{ + return pool_okay && ptr_into_pool_p (p); +} + + + +/**************** + * Warning: This code might be called by an interrupt handler + * and frankly, there should really be such a handler, + * to make sure that the memory is wiped out. + * We hope that the OS wipes out mlocked memory after + * receiving a SIGKILL - it really should do so, otherwise + * there is no chance to get the secure memory cleaned. + */ +void +secmem_term() +{ + if( !pool_okay ) + return; + + wipememory2( pool, 0xff, poolsize); + wipememory2( pool, 0xaa, poolsize); + wipememory2( pool, 0x55, poolsize); + wipememory2( pool, 0x00, poolsize); +#ifdef HAVE_MMAP + if( pool_is_mmapped ) + munmap( pool, poolsize ); +#endif + pool = NULL; + pool_okay = 0; + poolsize=0; + poollen=0; + unused_blocks=NULL; +} + + +void +secmem_dump_stats() +{ + if( disable_secmem ) + return; + fprintf(stderr, + "secmem usage: %u/%u bytes in %u/%u blocks of pool %lu/%lu\n", + cur_alloced, max_alloced, cur_blocks, max_blocks, + (ulong)poollen, (ulong)poolsize ); +} diff -uNr a/eucrypt/mpi/tests/Makefile b/eucrypt/mpi/tests/Makefile --- a/eucrypt/mpi/tests/Makefile false +++ b/eucrypt/mpi/tests/Makefile e613a174af5f4db157c16d4e5780b5ee563d8dda28821af7459162a1c01f0a6f12d18c23da54bf6f2a3a6287b174e6c28cc321aa5e167087617cb5fbd8462e8c @@ -0,0 +1,24 @@ +PROGRAM = test_mpi + +CXX = gcc +OBJECTS := $(patsubst %.c,%.o,$(wildcard *.c)) +FLAGS = -g -Wall +INCLUDE = -I ../include +MPI = ../bin/mpi.a +LIBS := $(MPI) + +.SUFFIXES: .o .c + +.c.o: + $(CXX) $(FLAGS) $(INCLUDE) -c $< -o $@ + +all: $(PROGRAM) + +$(PROGRAM): $(OBJECTS) + $(CXX) $(FLAGS) $(INCLUDE) -o $(PROGRAM) $(OBJECTS) $(LIBS) + +clean : + rm -rf nul core *flymake* *.o $(PROGRAM) *~ bin obj + +check-syntax: + $(CXX) -c $(FLAGS) $(INCLUDE) -o nul -Wall -S $(CHK_SOURCES) diff -uNr a/eucrypt/mpi/tests/test_mpi.c b/eucrypt/mpi/tests/test_mpi.c --- a/eucrypt/mpi/tests/test_mpi.c false +++ b/eucrypt/mpi/tests/test_mpi.c 85384bc9e48590da125a7440103ebc5549a2c1e10dd2335810c06f6bca4ca4f22f0626b0f625128f8d73de47c0a2aa9260f1014eacccc5cbdb2e37498347e99c @@ -0,0 +1,39 @@ +#include "mpi.h" +#include + +void err(char *msg) +{ + fprintf(stderr, "%s\n", msg); + exit(1); +} + +void terpri(FILE *fp) +{ + fprintf(fp, "\n"); +} + +int main(int ac, char **av) +{ + MPI a, b, y; + int r; + + r = secmem_init(1000); + if (r==0) err("secmem init"); + + a = mpi_alloc_secure(0); + b = mpi_alloc_secure(0); + y = mpi_alloc_secure(0); + mpi_fromstr(a, "0x1B0B206C488601"); + mpi_fromstr(b, "0x20E92FE28E1929"); + mpi_mul(y, a, b); + mpi_free(a); + mpi_free(b); + + mpi_print(stdout, y, 1); + mpi_free(y); + + terpri(stdout); + secmem_term(); + + return 0; +}